Take the most courses before their deadlines: sort by deadline, keep a max-heap of durations, and drop the longest when time runs over.
▼The problem
LeetCode 630 (Hard). courses[i] = [duration, lastDay]: course i takes duration days and must be finished by day lastDay. You take courses one at a time, starting on day 1. Return the maximum number of courses you can take. (This is not the graph Course Schedule: ../course-schedule and ../course-schedule-ii are topological sorts; this one is about deadlines, and the title card says so.)
Examples (LeetCode's): [[100,200],[200,1300],[1000,1250],[2000,3200]] → 3 (walked through in scene 6; all four would end on day 3300 > 3200), [[1,2]] → 1 and [[3,2],[4,3]] → 0 (each course alone runs past its own due day).
The solution
import heapq
def scheduleCourse(courses):
courses.sort(key=lambda c: c[1])
heap, time = [], 0
for dur, last in courses:
heapq.heappush(heap, -dur) # max heap
time += dur
if time > last:
time += heapq.heappop(heap)
return len(heap)Transcript
Course Schedule Three. Not prerequisites this time: deadlines. Each course takes some days and has a last day. Starting on day one, you take them one at a time. How many can you finish?
Four courses: one hundred days due by day two hundred, two hundred due by thirteen hundred, a thousand due by twelve fifty, and two thousand due by thirty-two hundred. Three fit. One course of one day, due day two, gives one. Three days due day two, and four due day three, gives zero.
The naive way tries every subset in deadline order and checks it: two to the n subsets, times n. Forty courses: over a trillion.
Better: sort by last day. Add each course to a running time, and keep the taken courses in a max heap. If the time passes this deadline, drop the longest course taken. The count stays the same, but the most time comes free.
In code, push each duration and add it to time. When late, pop the longest and subtract it. The heap's size is the answer.
Let's walk it. The hundred ends on day one hundred. The thousand ends on eleven hundred. The two hundred ends right on thirteen hundred. The two thousand would end on thirty-three hundred, too late, so the longest goes: the two thousand itself. Three courses.
Sorting is n log n, and each push or pop is log n: order n log n time, and order n space.
Sort by deadline, add each course, drop the longest when late. That's Course Schedule Three.