Editorial for Deadline Homework

Approach

Each assignment takes exactly one hour, so by time $d$ you can finish at most $d$ assignments.

Sort the assignments by deadline. As you scan them in that order, keep a min-heap containing the scores of the assignments you currently plan to do.

When you see an assignment with score $s_i$:

1. Add $s_i$ to the heap.
2. If the heap now contains more than $d_i$ assignments, remove the smallest score.

Why is this correct? After processing all assignments with deadline at most $d_i$, any valid plan can contain at most $d_i$ of them. If we currently have too many chosen assignments, removing the smallest score is always optimal, since it keeps the total score as large as possible.

At the end, the heap contains exactly the set of assignments in an optimal schedule, so the answer is the sum of its scores.

This runs in $O(n \log n)$ time.

Solution (Python)

import heapq

n = int(input())
assignments = [tuple(map(int, input().split())) for _ in range(n)]
assignments.sort()

chosen = []
total = 0

for deadline, score in assignments:
    heapq.heappush(chosen, score)
    total += score
    if len(chosen) > deadline:
        total -= heapq.heappop(chosen)

print(total)