Course Schedule III — Greedy Deadline Scheduling with a Max-Heap

Problem Statement#

Each course has a duration and a hard deadline by which it must be finished. Starting at time 0 and taking courses sequentially, return the maximum number of courses you can complete.

Constraints:

• 1 <= courses.length <= 10^4
• 1 <= duration, lastDay <= 10^4

Input:  [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3

Input:  [[1,2]]
Output: 1

Why This Problem Matters#

Course Schedule III is a Google priority queue interview classic that tests greedy intuition layered on a max-heap. It maps directly to real scheduling — task admission control, deadline-bound batch jobs, and CPU job scheduling under SLA.

The greedy "exchange argument" — drop the longest already-scheduled task when a new task overflows — is a transferable pattern. Once you internalize it, problems like IPO, Furthest Building, and Job Scheduling fall fast.

The Core Insight#

Sort courses by deadline. Walk through in order, adding each course's duration to a running time. If time exceeds the current deadline, drop the longest course in the schedule using a max-heap. This guarantees we always have the largest possible legal subset.

Visual Dry Run#

For [[100,200],[200,1300],[1000,1250],[2000,3200]]:

Solution (Optimal)#

import heapq
 
class Solution:
    def scheduleCourse(self, courses):
        courses.sort(key=lambda c: c[1])
        heap = []  # max-heap (negated)
        time = 0
        for dur, dl in courses:
            time += dur
            heapq.heappush(heap, -dur)
            if time > dl:
                time += heapq.heappop(heap)  # popped is negative
        return len(heap)

var scheduleCourse = function(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    const heap = new MaxHeap();
    let time = 0;
    for (const [dur, dl] of courses) {
        time += dur;
        heap.push(dur);
        if (time > dl) time -= heap.pop();
    }
    return heap.size();
};

Time: O(n log n) — sort plus n heap operations. Space: O(n) — heap of admitted course durations.

Common Mistakes#

• Sorting by duration instead of deadline — wrong ordering
• Using a min-heap and trying to skip the largest — defeats the swap logic
• Forgetting to add duration before checking the deadline — order matters
• Returning the length of the input, not the heap
• Reading the heap as a sorted list — only the root is guaranteed sorted

Interview Tips#

• Frame it as exchange argument: at each step the schedule is the optimal set among the courses considered
• Walk through both branches: course fits cleanly versus course causes overflow
• Note that even when we drop a course, time only decreases, so future courses can fit
• Mention this is the same template as LeetCode 1235 Job Scheduling

Follow-up Questions#

• Each course has a profit instead of a unit count? Use weighted job scheduling DP
• Courses can be paused and resumed? Different problem — preemptive scheduling
• Multiple parallel CPUs? Use multiple heaps or load balancing
• Variable start time per course? Add an availability constraint to the sort key
• What if deadlines can change over time? Use an indexed priority queue

Key Takeaways#

• Sort by deadline, then use a max-heap of durations
• When time overflows, drop the longest course — greedy exchange argument
• O(n log n) time, O(n) space
• Heap size at the end is the answer
• Same pattern: deadline scheduling, IPO with capital cap, Furthest Building with ladders
• Interview talking point: prove correctness via exchange argument
• Foundational greedy + heap technique for FAANG scheduling questions