Course Schedule III (LeetCode 630)
You are offered n online courses. courses[i] = [duration_i, lastDay_i]: course i takes duration_i days in a row, and it has to be finished no later than day lastDay_i. You start on day 1 and can only follow one course at a time, so the courses you choose run back to back.
Return the largest number of courses you can complete.
Worked Examples
courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]3courses = [[1,2]]1courses = [[3,2],[4,3]]0⚖️Formal Constraints & Bounds
1 <= courses.length <= 1041 <= duration_i, lastDay_i <= 104
Core Insight
Go through the courses by last day and take each one; when the total runs past the current last day, dropping the longest course taken keeps the same count and frees the most days for what comes next.
Real-World Scenario & Production Applications
Admitting jobs into a queue where each job has a length and a due time: a scheduler that accepts every job, and evicts the longest accepted one whenever a due time would be missed, keeps the number of on-time jobs as high as possible. The same rule appears in classic single-machine scheduling (maximize the number of on-time jobs).
Step-by-Step Execution Trace Table
Input courses = [[100,200],[200,1300],[1000,1250],[2000,3200]], sorted by last day: [100,200], [1000,1250], [200,1300], [2000,3200].
| Step | Course [duration, last_day] | total_time after taking it | total_time > last_day? | Action | max_heap (durations taken) |
|---|---|---|---|---|---|
| 1 | [100, 200] | 100 | No | Keep | {100} |
| 2 | [1000, 1250] | 1100 | No | Keep | {1000, 100} |
| 3 | [200, 1300] | 1300 | No (equal is fine) | Keep | {1000, 200, 100} |
| 4 | [2000, 3200] | 3300 | Yes | Pop the longest, 2000: total_time = 1300 | {1000, 200, 100} |
| End | return len(max_heap) = 3 |
| 1 | Take every course, and when the days run out, undo the single worst choice made so far: the longest course taken. |
| 2 | `max_heap` always holds the most courses that fit the deadlines seen so far, with the smallest possible `total_time`. |
| 3 | Sort `courses` by last day; for each `duration, last_day`: add `duration` to `total_time`, push `-duration`; if `total_time > last_day`, pop the longest and subtract it; `return len(max_heap)`. |
| 4 | The trap: sort by `last_day`, not by `duration`, or a short course with a late deadline pushes out a course whose early deadline was still reachable. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some greedy problems can't be solved by picking the right item up front, because you only learn later that an earlier pick was a mistake. Greedy with Regret takes every item as it comes, keeps the picks in a heap, and the moment a limit is broken it undoes the single worst pick. For Course Schedule III: go through courses by deadline, take each one, and if the running total of days now misses the current deadline, drop the longest course taken so far.
🏟️ The Analogy: Packing a Suitcase Against a Weight Limit
You pack items in the order you need them, and at each checkpoint the bag must be under the limit. Whenever you are over, you don't unpack everything and start again: you pull out the single heaviest item. The count of items stays as high as it can be, and the bag is as light as it can be, which leaves the most room for what comes next.
🔑 Why It Works
After each course, max_heap holds the most courses that fit the deadlines seen so far, and among all such sets the one with the smallest total_time. Dropping the longest course keeps the count and frees the most days, so no later course is ever blocked by a choice we could have made better.
Sorting by
durationinstead oflast_day: shortest-first ignores deadlines. On[[3,3],[1,3],[1,6],[2,3]]shortest-first takes the two 1-day courses, then the 2-day course misses day 3 and gets dropped with the 3-day one: 2 courses instead of 3.Checking before taking:
if total_time + duration <= last_day: take itnever revisits old picks, so one long early course can block several short later ones. Take the course first, then drop the longest if the deadline breaks.Dropping the course just added instead of the longest: the new course may be short; dropping the longest one frees the most days for later courses while keeping the same count.
Returning
total_time: the question asks how many courses; the answer islen(max_heap).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest number of courses", each with a length and a last day, done one at a time: you pick as many items as possible under deadlines, and a pick that looked fine early can block several later ones. That is the signal to take greedily and keep a heap to undo the worst pick: Greedy with Regret.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each course, max_heap holds the most courses that all finish by their last days, and among all sets of that size it has the smallest total_time; the rule is: push -duration, and if total_time > last_day, pop the longest and subtract it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
courses.sort(key=lambda c: c[1])on[[3,3],[1,3],[1,6],[2,3]]: sorted by last day the answer is 3; sorted by duration it is 2, because the two 1-day courses go first and the 2-day and 3-day courses both miss day 3.if total_time > last_daymust be strict: finishing exactly on the last day is on time. In Example 1 the third course taken ends exactly on day 1300 and stays.longest = -heapq.heappop(max_heap): Python's heap is a min-heap, so durations are stored negated; forgetting the minus pops the shortest course instead of the longest.A course with
duration > last_daycan never fit: it is taken, pushed, and popped again at once (Example 3,[[3,2],[4,3]], returns 0), so no special case is needed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy with Regret. I sort the courses by their last day and walk through them, taking every course: I add its duration to a running total and push it onto a max-heap. If the total now passes this course's last day, I pop the longest course I've taken and subtract it. That keeps the count the same as before this course but makes the total as small as possible, so every later course has the most room to fit; and since all earlier courses have earlier deadlines, they still fit too. The trap is the sort key: it must be the last day, not the duration, or a short course with a late deadline can crowd out one whose early deadline was reachable. The answer is the heap's size. Sorting and the heap give
O(N log N)time andO(N)space.
Complexity & Mathematical Proof
O(N log N)
Look at the code: courses.sort(key=lambda c: c[1]) costs O(N log N). The loop runs once per course; each iteration does one heappush (O(log N)) and at most one heappop (O(log N)) on a heap that never holds more than N items. Total: O(N log N) + N · O(log N) = O(N log N).
O(N)
max_heap holds at most N negated durations: O(N). Python's sort needs up to O(N) extra memory as well. The answer is one integer.
T(N) = O(N log N) + N · (O(log N) + O(log N)) = O(N log N)
Derivation Progression
O(N log N)
courses.sort(key=lambda c: c[1]).
N × O(log N)
One heappush per course onto a heap of at most N items.
at most N × O(log N)
Each course is popped at most once, since it is pushed once.
O(N log N)
The sort and the heap work have the same order.
Variable Definitions
Number of courses, len(courses)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): max_heap plus the sort's working memory
O(1): one integer
Boundary Best / Worst Cases
: the sort runs even if no course is ever popped
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the largest number of courses", "finished no later than day lastDay", "one course at a time". Count-maximizing selection under deadlines, where an early pick can block later ones: Greedy with Regret (take everything, undo the longest with a max-heap).
courses, durations and last days . Brute force over subsets is ; the budget is time and space.
At scale, the heap holds every accepted item; if items arrive as a stream sorted by due time, the same loop runs online, but items that arrive out of due-time order break the invariant, so buffer and sort them first.
Course Schedule III (LeetCode 630)
You are offered n online courses. courses[i] = [duration_i, lastDay_i]: course i takes duration_i days in a row, and it has to be finished no later than day lastDay_i. You start on day 1 and can only follow one course at a time, so the courses you choose run back to back.
Return the largest number of courses you can complete.
Worked Examples
courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]3courses = [[1,2]]1courses = [[3,2],[4,3]]0⚖️Formal Constraints & Bounds
1 <= courses.length <= 1041 <= duration_i, lastDay_i <= 104
Core Insight
Go through the courses by last day and take each one; when the total runs past the current last day, dropping the longest course taken keeps the same count and frees the most days for what comes next.
Real-World Scenario & Production Applications
Admitting jobs into a queue where each job has a length and a due time: a scheduler that accepts every job, and evicts the longest accepted one whenever a due time would be missed, keeps the number of on-time jobs as high as possible. The same rule appears in classic single-machine scheduling (maximize the number of on-time jobs).
Step-by-Step Execution Trace Table
Input courses = [[100,200],[200,1300],[1000,1250],[2000,3200]], sorted by last day: [100,200], [1000,1250], [200,1300], [2000,3200].
| Step | Course [duration, last_day] | total_time after taking it | total_time > last_day? | Action | max_heap (durations taken) |
|---|---|---|---|---|---|
| 1 | [100, 200] | 100 | No | Keep | {100} |
| 2 | [1000, 1250] | 1100 | No | Keep | {1000, 100} |
| 3 | [200, 1300] | 1300 | No (equal is fine) | Keep | {1000, 200, 100} |
| 4 | [2000, 3200] | 3300 | Yes | Pop the longest, 2000: total_time = 1300 | {1000, 200, 100} |
| End | return len(max_heap) = 3 |
| 1 | Take every course, and when the days run out, undo the single worst choice made so far: the longest course taken. |
| 2 | `max_heap` always holds the most courses that fit the deadlines seen so far, with the smallest possible `total_time`. |
| 3 | Sort `courses` by last day; for each `duration, last_day`: add `duration` to `total_time`, push `-duration`; if `total_time > last_day`, pop the longest and subtract it; `return len(max_heap)`. |
| 4 | The trap: sort by `last_day`, not by `duration`, or a short course with a late deadline pushes out a course whose early deadline was still reachable. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Some greedy problems can't be solved by picking the right item up front, because you only learn later that an earlier pick was a mistake. Greedy with Regret takes every item as it comes, keeps the picks in a heap, and the moment a limit is broken it undoes the single worst pick. For Course Schedule III: go through courses by deadline, take each one, and if the running total of days now misses the current deadline, drop the longest course taken so far.
🏟️ The Analogy: Packing a Suitcase Against a Weight Limit
You pack items in the order you need them, and at each checkpoint the bag must be under the limit. Whenever you are over, you don't unpack everything and start again: you pull out the single heaviest item. The count of items stays as high as it can be, and the bag is as light as it can be, which leaves the most room for what comes next.
🔑 Why It Works
After each course, max_heap holds the most courses that fit the deadlines seen so far, and among all such sets the one with the smallest total_time. Dropping the longest course keeps the count and frees the most days, so no later course is ever blocked by a choice we could have made better.
Sorting by
durationinstead oflast_day: shortest-first ignores deadlines. On[[3,3],[1,3],[1,6],[2,3]]shortest-first takes the two 1-day courses, then the 2-day course misses day 3 and gets dropped with the 3-day one: 2 courses instead of 3.Checking before taking:
if total_time + duration <= last_day: take itnever revisits old picks, so one long early course can block several short later ones. Take the course first, then drop the longest if the deadline breaks.Dropping the course just added instead of the longest: the new course may be short; dropping the longest one frees the most days for later courses while keeping the same count.
Returning
total_time: the question asks how many courses; the answer islen(max_heap).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The largest number of courses", each with a length and a last day, done one at a time: you pick as many items as possible under deadlines, and a pick that looked fine early can block several later ones. That is the signal to take greedily and keep a heap to undo the worst pick: Greedy with Regret.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After each course, max_heap holds the most courses that all finish by their last days, and among all sets of that size it has the smallest total_time; the rule is: push -duration, and if total_time > last_day, pop the longest and subtract it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
courses.sort(key=lambda c: c[1])on[[3,3],[1,3],[1,6],[2,3]]: sorted by last day the answer is 3; sorted by duration it is 2, because the two 1-day courses go first and the 2-day and 3-day courses both miss day 3.if total_time > last_daymust be strict: finishing exactly on the last day is on time. In Example 1 the third course taken ends exactly on day 1300 and stays.longest = -heapq.heappop(max_heap): Python's heap is a min-heap, so durations are stored negated; forgetting the minus pops the shortest course instead of the longest.A course with
duration > last_daycan never fit: it is taken, pushed, and popped again at once (Example 3,[[3,2],[4,3]], returns 0), so no special case is needed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy with Regret. I sort the courses by their last day and walk through them, taking every course: I add its duration to a running total and push it onto a max-heap. If the total now passes this course's last day, I pop the longest course I've taken and subtract it. That keeps the count the same as before this course but makes the total as small as possible, so every later course has the most room to fit; and since all earlier courses have earlier deadlines, they still fit too. The trap is the sort key: it must be the last day, not the duration, or a short course with a late deadline can crowd out one whose early deadline was reachable. The answer is the heap's size. Sorting and the heap give
O(N log N)time andO(N)space.
Complexity & Mathematical Proof
O(N log N)
Look at the code: courses.sort(key=lambda c: c[1]) costs O(N log N). The loop runs once per course; each iteration does one heappush (O(log N)) and at most one heappop (O(log N)) on a heap that never holds more than N items. Total: O(N log N) + N · O(log N) = O(N log N).
O(N)
max_heap holds at most N negated durations: O(N). Python's sort needs up to O(N) extra memory as well. The answer is one integer.
T(N) = O(N log N) + N · (O(log N) + O(log N)) = O(N log N)
Derivation Progression
O(N log N)
courses.sort(key=lambda c: c[1]).
N × O(log N)
One heappush per course onto a heap of at most N items.
at most N × O(log N)
Each course is popped at most once, since it is pushed once.
O(N log N)
The sort and the heap work have the same order.
Variable Definitions
Number of courses, len(courses)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N): max_heap plus the sort's working memory
O(1): one integer
Boundary Best / Worst Cases
: the sort runs even if no course is ever popped
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the largest number of courses", "finished no later than day lastDay", "one course at a time". Count-maximizing selection under deadlines, where an early pick can block later ones: Greedy with Regret (take everything, undo the longest with a max-heap).
courses, durations and last days . Brute force over subsets is ; the budget is time and space.
At scale, the heap holds every accepted item; if items arrive as a stream sorted by due time, the same loop runs online, but items that arrive out of due-time order break the invariant, so buffer and sort them first.