Course Schedule III: Maximizing Courses with Greedy + Heap

Imagine you are registering for classes, and every course has a duration and a hard deadline. You can only take one course at a time, and you need to finish each course before its deadline expires. How do you pick the maximum number of courses to take?

That is exactly what LeetCode 630: Course Schedule III asks. You are given an array of courses where courses[i] = [duration, deadline]. You start at time 0 and can only take courses sequentially. The goal is to maximize the total number of courses you complete.

Why this problem matters

Course Schedule III is a classic example of the greedy + heap pattern. It teaches you that sometimes the greedy choice is not just about picking the best option right now, but also about being willing to undo a previous choice when a better trade-off appears.

This "swap out the worst" technique shows up in scheduling problems, resource allocation, and any scenario where you want to maximize the count of items that fit within constraints. The same pattern drives problems like IPO, where you greedily pick the most profitable project you can afford.

What makes this problem tricky is that a naive greedy approach (pick the shortest course first, or pick the earliest deadline first) does not work on its own. You need both: sort by deadline, then use a max-heap to swap out long courses when they cause you to miss a deadline.

The approach

The algorithm has two key ideas:

1. Sort courses by deadline. Processing courses in deadline order guarantees that when you try to add a course, all previously added courses have deadlines at least as early. If the current course fits, great. If not, you can swap it with the longest course you have already taken.

2. Use a max-heap to track durations. The heap lets you quickly find the longest course you have committed to. If adding a new course pushes your total time past its deadline, pop the longest course from the heap. This swap either reduces your total time (if the new course is shorter than what you removed) or keeps it the same. Either way, the count stays the same or stays valid. You never lose a course from your count without replacing it.

Why does swapping work? Because you sorted by deadline. Every course you already added has a deadline that is no later than the current course's deadline. If you remove the longest one and replace it with the current one (which is shorter or equal, otherwise you would not need to swap), the total time can only decrease. A shorter total time means all the earlier deadlines are still satisfied.

import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])
    heap = []
    time = 0

    for duration, deadline in courses:
        heapq.heappush(heap, -duration)
        time += duration
        if time > deadline:
            time += heapq.heappop(heap)

    return len(heap)

Step-by-step walkthrough

Let's trace through the example courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]. After sorting by deadline, we get [[100,200],[1000,1250],[200,1300],[2000,3200]].

Complexity analysis

Time: Sorting takes O(n log n). Then we iterate through all n courses, and each heap push/pop is O(log n). Total: O(n log n).

Space: The heap can hold up to n elements, so O(n).

Edge cases to watch for

• Single course: If there is only one course and its duration fits within its deadline, take it. If not, return 0.
• All courses have the same deadline: The algorithm still works. It will keep pushing shorter courses and popping longer ones to fit as many as possible before the shared deadline.
• Duration exceeds deadline: A course like [500, 100] can never be taken. The algorithm handles this naturally. After pushing 500, time = 500 > 100, so it pops 500 right back off. The heap size does not grow.
• Courses already sorted: No special handling needed. Sorting a sorted list is still O(n log n) in the worst case but often O(n) with Timsort.
• All courses fit: If the total of all durations is within every deadline, the heap never needs to pop. You take everything.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently:

1. Sort-then-greedily-process

Sorting the input by one dimension (here, deadline) to impose an order that makes the greedy choice valid:

courses.sort(key=lambda x: x[1])
for duration, deadline in courses:
    # process in deadline order

You see this pattern in interval scheduling (Meeting Rooms), activity selection, and many other greedy problems. The key insight is always the same: sorting by one property (deadline, end time, profit threshold) creates an invariant that makes your greedy decisions provably optimal.

2. Max-heap for tracking and swapping the worst element

Using a max-heap to efficiently find and remove the element that hurts you the most:

heapq.heappush(heap, -duration)
if time > deadline:
    time += heapq.heappop(heap)  # removes the largest duration

Python's heapq is a min-heap, so you negate values to simulate a max-heap. This is a common Python idiom. The heap lets you answer "what is the longest course I have committed to?" in O(1) and remove it in O(log n). Without the heap, you would need O(n) to find the maximum each time.

From understanding to recall

The logic of this solution is elegant: sort by deadline, greedily add each course, and swap out the longest one when you overflow. Reading it, it makes sense. But writing it from scratch in an interview requires remembering the sort key, the negation trick for the max-heap, the condition if time > deadline, and the fact that heappop returns the negated max.

Those details are exactly what spaced repetition drills. You practice writing the sort, the heap push, and the swap logic from memory at increasing intervals. After a few rounds, the pattern becomes automatic. You stop worrying about whether it is time > deadline or time >= deadline (it is >, because equal means it fits exactly). You just write it.

Related posts

• Course Schedule - prerequisite graph traversal
• Meeting Rooms - interval scheduling with sorting
• IPO - greedy + heap selection pattern

CodeBricks breaks Course Schedule III into its sort-by-deadline and max-heap-swap building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the greedy + heap pattern is automatic. When a scheduling optimization problem shows up in your interview, you do not hesitate. You just write it.