Question and Answer from L4-M2
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()