Haroid and Dan's Homework Deal

Added: 2025-09-13 08:21:41

Question Image

Haroid and Dan's Homework Deal

Answer

✏️ Edit
def solve():
    # Step 1: Take input
    n = int(input().strip())  # number of homeworks
    
    # Read amounts (profits)
    amounts_input = input().strip().split()
    amounts = [int(x) for x in amounts_input]
    
    # Read deadlines
    deadlines_input = input().strip().split()
    deadlines = [int(x) for x in deadlines_input]
    
    # Step 2: Pair each homework as (amount, deadline)
    jobs = []
    for i in range(n):
        jobs.append((amounts[i], deadlines[i]))
    
    # Step 3: Sort jobs by amount (profit) in descending order
    for i in range(len(jobs)):
        for j in range(i + 1, len(jobs)):
            if jobs[i][0] < jobs[j][0]:
                jobs[i], jobs[j] = jobs[j], jobs[i]
    
    # Step 4: Find maximum deadline
    max_deadline = 0
    for d in deadlines:
        if d > max_deadline:
            max_deadline = d
    
    # Step 5: Create schedule slots
    slots = [0] * (max_deadline + 1)  # index = time slot, value = profit
    
    total_money = 0
    
    # Step 6: Schedule jobs greedily
    for amount, deadline in jobs:
        # Try to schedule this job at the latest possible slot before its deadline
        t = deadline
        while t > 0:
            if slots[t] == 0:  # empty slot
                slots[t] = amount
                total_money += amount
                break
            t -= 1
    
    # Step 7: Print the result
    print(total_money)


# Run the function
solve()