Course Schedule III

Course Schedule III is a greedy classic that pairs sorting with a max-heap. It teaches a powerful move: take everything optimistically, then undo your worst decision the moment you break a rule.

The slow way first

The brute force is to try every subset of courses, check each ordering, and keep the largest valid set. With n courses that is O(2ⁿ) subsets — hopeless beyond a handful of courses.

The question to ask: in what order should I even consider courses, and what do I do when one does not fit? If we are greedy about deadlines and clever about what to drop, we never need to enumerate subsets.

The idea: take everything, then drop your longest

Sort the courses by deadline, so we decide them in the order they must finish. Walk left to right keeping a running total of days spent, and push each course duration onto a max-heap.

Whenever total exceeds the current course deadline, we have overcommitted. Pop the longest course taken so far (the heap top) and remove its time. That single swap frees the most days while costing us at most one course — and the course count can only stay the same or improve.

The key insight: dropping the longest course (not the current one) is always at least as good, because it frees the most time for the same one-course cost. The heap makes finding that longest course an O(log n) operation.

Walk through it

Step through the animation. Courses are shown as duration / deadline, already sorted by deadline. We keep adding to total and pushing onto the heap. At the 1000/1250 course total hits 1300, past the 1250 deadline, so we pop the longest course taken (1000) and swap it out. The final heap size, 3, is the answer.

Pseudocode

sort courses by deadline (lastDay)
make an empty max-heap and total = 0
for each (duration, deadline) in courses:
    total = total + duration
    push duration onto the max-heap
    if total > deadline:                 # we overflowed
        longest = pop the max from the heap
        total = total - longest          # undo the worst decision
return size of the heap                   # courses we kept

The Python solution

def schedule_course(courses):
    courses.sort(key=lambda c: c[1])
    heap, total = [], 0
    for dur, end in courses:
        total += dur
        heapq.heappush(heap, -dur)
        if total > end:
            longest = -heapq.heappop(heap)
            total -= longest
    return len(heap)

• courses.sort(key=lambda c: c[1]) orders by deadline so we never decide a later-deadline course before an earlier one.
• heap is a max-heap; Python only has a min-heap, so we push the negated duration (-dur) to flip the order.
• total += dur optimistically takes the course, then heappush records its duration.
• Line 7 is the overflow check. When total > end, we have committed to more days than this deadline allows.
• longest = -heapq.heappop(heap) pulls the biggest duration (un-negated). Subtracting it frees the most time, so the rest of the schedule stays legal while the course count never drops.

Complexity

The heap holds at most every course, so it costs O(n) extra space. The dominant cost is the sort plus n heap operations: O(n log n) overall.

When this pattern shows up

Practice