433. Course Schedule III
You are picking from n online courses. Course i takes duration_i consecutive days of work and must be fully wrapped up on or before day lastDay_i. The clock starts on day 1, you can only study one course at a time, and the moment you finish one course you may begin the next — no idle days needed.
Your function receives a list courses where courses[i] = [duration_i, lastDay_i]. Return one integer: the largest number of courses you can complete while respecting every chosen course's deadline.
Example 1:
Input: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation: Take course 0 first (done on day 100 ≤ 200), then course 2 (done on day 1100 ≤ 1250), then course 1 (done on day 1300 ≤ 1300). Course 3 would finish on day 3300 > 3200, so three is the best possible.
Example 2:
Input: courses = [[1, 2]]
Output: 1
Explanation: One day of work, due by day 2 — it fits.
Constraints:
- 1 ≤ n ≤ 5000
- 1 ≤ duration_i, lastDay_i ≤ 10⁴
Hints:
Suppose you already knew WHICH courses to take. In what order should you take them? Finishing-deadline order (earliest lastDay first) is always safe — so sort by deadline and the only question left is which courses to keep.
Scan in deadline order and optimistically take every course. When the running total of days overshoots the current deadline, you must give something back — and dropping the single longest course taken so far frees the most days while costing only one course. A max-heap of taken durations hands you that course in O(log n).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Expected output: 3