Most courses before the deadlines
Take as many courses as possible when each has a length and a last day, by sorting by deadline and dropping the longest course whenever the schedule overruns. About 22 minutes.
Deadlines set the order
Each course takes some days and must be finished by its last day. You take them one after another, with no gaps, and want to take as many as possible.
Sort the courses by last day. If you take a set of courses, doing them in order of last day is always the safest schedule, because the courses with the tightest deadlines go first. Now the only question is which courses to include.
Swap out the longest
Add courses in deadline order, keeping a running total of days used. If a new course makes the total pass its last day, one course must go.
Drop the longest course taken so far, possibly the new one. Swapping it out keeps the same count but uses the fewest days, so later courses have the most room. A max-heap of lengths gives the longest in logarithmic time.
heapq.heappush(heap, -length) longest = -heapq.heappop(heap)
Take 50. Time used 50, within day 100.
Why drop the longest course when the schedule runs over?
- AIt frees the most time and loses only one course
- BShort courses are always worth more
- CThe latest deadline is always the problem
Show the answer
It frees the most time and loses only one course. Removing any course loses one from the count, so remove the one that frees the most days.
Most courses
You are given courses, where courses[i] = [length, lastDay]: the course takes length days and must be finished on or before lastDay. You take courses one at a time, starting on day 1 with no gaps, and each course must be completed before the next starts. Return the largest number of courses you can take.
courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] → 3
1 ≤ courses.length ≤ 10,000 · 1 ≤ length, lastDay ≤ 10,000