Course Schedule III

Course Schedule III

What is this problem about?

The Course Schedule III interview question is significantly different from the first two. You are given a list of courses, where each course has a duration and a lastDay (deadline). You can only take one course at a time, and a course must be completed by its lastDay. Your goal is to find the maximum number of courses you can take.

Why is this asked in interviews?

Amazon and Salesforce use the Course Schedule III coding problem to test a candidate's mastery of Greedy algorithms and Heaps (Priority Queues). Unlike the previous versions which were about connectivity, this is about scheduling and resource allocation. It evaluates if you can identify a strategy that minimizes "regret" by swapping long courses for shorter ones to fit more courses into the schedule.

Algorithmic pattern used

This problem is solved using a Greedy approach with a Max-Heap.

1. Sort: Sort all courses by their lastDay (deadlines). This ensures you process courses in the order they must be finished.
2. Iterate: Maintain a running total of the currentTime.
3. Add: For each course, add its duration to currentTime. Push the duration into a Max-Heap.
4. Check and Swap: If currentTime exceeds the current course's lastDay, remove the longest course seen so far from the heap (the top of the max-heap) and subtract its duration from currentTime. This ensures that at any point, you have taken the maximum possible courses within the time limit by always discarding the most time-consuming ones when a conflict occurs.

Example explanation

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

1. Sort by deadline: [100, 200], [1000, 1250], [200, 1300], [2000, 3200].
2. Course 1: currentTime = 100. (Valid). Heap: [100].
3. Course 2: currentTime = 1100. (Valid, 1100 < 1250). Heap: [1000, 100].
4. Course 3: currentTime = 1300. (Valid, 1300 <= 1300). Heap: [1000, 200, 100].
5. Course 4: currentTime = 3300. (Invalid, 3300 > 3200).
   • Max in heap is 1000. Remove it.
   • currentTime = 3300 - 1000 = 2300.
   • Add current course duration (2000). Heap: [2000, 200, 100]. Result: 3 courses.

Common mistakes candidates make

• Sorting by Duration: Sorting by duration doesn't account for deadlines. You must sort by the "last day" to be greedy about time availability.
• Not using a Heap: Trying to use a simple list and sorting it repeatedly, which leads to O(N^2 log N) instead of O(N log N).
• Wrong Heap Type: Using a Min-Heap instead of a Max-Heap. You want to remove the longest course to save the most time.

Interview preparation tip

This is a classic "Interval Scheduling with Regret" problem. Whenever you need to fit the "most" items into a fixed space/time and you can swap items, a Greedy approach with a Priority Queue is a strong candidate.