Course Schedule III - Video Solutions

Problem Overview: You are given courses where each course has a duration and a deadline. The goal is to take the maximum number of courses such that the total time spent never exceeds the deadline of any course you take.

Approach 1: Greedy with Max-Heap (Priority Queue) (Time: O(n log n), Space: O(n))

The key insight is that earlier deadlines should be handled first. Start by sorting all courses by their deadline using sorting. Then iterate through the courses and keep track of the total time spent. Each time you take a course, add its duration to the running total and push that duration into a max-heap from the heap (priority queue) category.

If the total time exceeds the current course's deadline, remove the course with the longest duration from the heap. This works because replacing a long course with a shorter one frees up time while keeping the course count high. The heap always stores durations of the courses you have chosen so far, and removing the maximum duration ensures the schedule remains feasible.

This greedy strategy works because deadlines enforce a natural order, and removing the longest course provides the best chance of fitting more courses later. The heap operations (push and pop) take O(log n), so the overall complexity becomes O(n log n) after sorting. This is the most efficient and widely accepted solution using concepts from greedy algorithms and array processing.

Approach 2: Dynamic Programming (Time: O(n * D), Space: O(n * D))

Dynamic programming models the problem as selecting courses while tracking the total time spent. First sort courses by deadline. Define a DP state where dp[i][t] represents whether it is possible to finish some subset of the first i courses using exactly t time. For each course, you either skip it or include it if the resulting total time does not exceed its deadline.

Transitions update the DP table by checking whether adding the current course duration keeps the schedule valid. The maximum number of courses can then be derived from the valid states. While this approach clearly expresses the decision process, it becomes expensive when deadlines are large because the DP dimension grows with total time.

Recommended for interviews: Interviewers expect the greedy + max-heap solution. Sorting by deadline shows you understand the scheduling constraint, and using a heap to drop the longest course demonstrates strong algorithmic intuition. The dynamic programming formulation shows correctness reasoning but is rarely optimal for production or interview settings due to higher time and space costs.