Course Schedule III LeetCode 630 — Greedy

LeetCode 630 Course Schedule III gives you an array of courses where each course is represented as [duration, lastDay]. You must take courses one at a time in any order. A course can only be completed if you start it early enough that you finish it on or before its lastDay deadline. Courses are taken sequentially — you cannot work on two courses at once — so taking one course delays the start of all subsequent courses.

Your goal is to find the maximum number of courses you can take. You do not need to return the actual course list, just the count. This makes it a pure optimization problem: choose a subset of courses and an order to take them such that every chosen course finishes by its deadline, and the subset is as large as possible.

The challenge is that courses conflict with each other through shared time: taking a long course early can push later courses past their deadlines. Choosing which courses to take — and in what order — requires a strategy that balances duration and deadline together, not just one factor alone.

A natural first instinct is to sort courses by duration — shortest first — and greedily take as many as possible. This maximizes the number of courses you can fit in a given window, but completely ignores deadlines. A sequence of short courses might all finish before their deadlines, but it might also cause you to miss the deadline for a critical short course that appears later in the sorted order.

Sorting by deadline alone is also insufficient. If you sort purely by deadline and greedily take every course in that order, you might include a very long course early on that consumes a huge block of time, making all subsequent courses miss their deadlines. A long course at the front can block more shorter courses than the count benefit it provides.

The fundamental issue is that duration and deadline are coupled constraints. A course with a tight deadline must be taken early, but if it has a long duration, it blocks other courses. You cannot optimize for one dimension independently — the correct strategy must account for both simultaneously.

The optimal algorithm sorts all courses by their deadline (lastDay) in ascending order. You then iterate through the sorted courses one by one, maintaining a running time counter that tracks how many days have elapsed if you were to take all courses seen so far. You also maintain a max-heap of the durations of all courses you have tentatively accepted.

For each course, you add its duration to the running time and push it onto the max-heap. If the running time now exceeds the course's deadline, you have a conflict. You resolve it by popping the maximum duration from the heap — removing the longest course accepted so far. This reduces the running time by the maximum possible amount with only one removal, maintaining the best possible schedule with the same count (or the same schedule with a shorter total time if no pop is needed).

The crucial invariant is that the heap always contains the optimal set of courses to take up to the current deadline. When you pop the maximum after an overflow, you are either removing the course you just added (if it was the longest), or swapping it for a shorter previously accepted course — in both cases the running time decreases and the count stays the same or the schedule becomes strictly better for future courses.

The correctness of this greedy strategy is proven by an exchange argument. Suppose there exists an optimal solution that differs from the greedy solution at some course. Consider the moment when the greedy algorithm makes a swap: it removes the longest course in the heap and keeps the current course (or vice versa). If the removed course had a longer duration, then replacing it with the shorter current course results in the same or lower running time for all subsequent courses, which can only help (never hurt) their feasibility.

More formally: if the greedy heap contains a set S of courses and the optimal solution contains a different set S*, and |S*| > |S|, then some course in S* is not in S. By the exchange argument, swapping a course in S for that course — using the greedy's max-heap invariant — produces a schedule that is at least as good as S with the same count. This contradicts the assumption that |S| is not optimal.

The max-heap is the mechanism that makes the exchange argument constructive: it always tells you which course to remove to free up the maximum time, and removing the maximum-duration course can only improve the feasibility of all future courses in the sorted-by-deadline order.

Python's heapq module implements a min-heap, but this problem requires a max-heap to efficiently pop the largest duration. The standard workaround is to negate durations when pushing: push -duration instead of duration. When popping, negate the result to recover the original positive duration. The heap invariant is preserved because negating reverses the comparison order.

Track a running integer time variable that accumulates durations. After pushing each new course and potentially popping the maximum, the heap size gives you the current count of accepted courses. There is no need to track which specific courses are in the heap — only their durations matter for the time calculation, and only the count matters for the answer.

Edge cases are handled cleanly by this approach. If a course's duration alone exceeds its deadline (duration > lastDay), it will always be pushed then immediately popped (since time > lastDay after adding it and it would be the max or swapped for a longer one). The algorithm handles this without any special-case check.

Python solution: import heapq. def scheduleCourse(courses): courses.sort(key=lambda c: c[1]); heap=[]; time=0. For d,last in courses: heapq.heappush(heap,-d); time+=d; if time>last: time+=heapq.heappop(heap). Return len(heap). Time complexity: O(n log n) for the sort plus O(n log n) for n heap operations each taking O(log n). Space complexity: O(n) for the heap in the worst case where all courses are accepted.

Java solution: public int scheduleCourse(int[][] courses) { Arrays.sort(courses, (a,b)->a[1]-b[1]); PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder()); int time=0; for(int[] c:courses){ pq.offer(c[0]); time+=c[0]; if(time>c[1]){ time-=pq.poll(); } } return pq.size(); } Java uses PriorityQueue with reverseOrder comparator for a natural max-heap, so no negation is needed. The logic is otherwise identical to the Python solution.

Both solutions run in O(n log n) time and O(n) space. The sort dominates in practice. The heap never grows beyond n elements and the total work across all heap operations is O(n log n). This is optimal for this problem — any correct solution must at minimum read all courses, and the sorting lower bound is O(n log n) for comparison-based approaches.

Course Schedule I (LeetCode 207) and Course Schedule II (LeetCode 210) use topological sort rather than greedy. They ask whether a valid course order exists given prerequisite constraints — a graph cycle detection problem. Course Schedule III is a completely different problem family despite the naming: it has no prerequisites and uses greedy + heap rather than topological sort.

Task Scheduler (LeetCode 621) and Meeting Rooms II (LeetCode 253) are the closest relatives. Task Scheduler uses a max-heap to schedule tasks with cooldown constraints, minimizing total time. Meeting Rooms II uses a min-heap to track room release times and find the minimum number of rooms needed. All three problems share the pattern of using a heap to manage time-based scheduling conflicts greedily.

The job scheduling family — including Job Scheduling in One Machine (interval scheduling maximization), Weighted Job Scheduling, and LeetCode 1235 Maximum Profit in Job Scheduling — all build on greedy or DP approaches to select non-overlapping or sequentially-feasible jobs. Course Schedule III is the purest heap-greedy variant in this family, making it an excellent entry point before tackling the weighted variants that require DP.