Course Schedule III

Problem

Given courses as [duration, last_day] pairs, return the maximum number of courses that can be taken so that each finishes by its last day, one course at a time.

Sort by deadline and greedily add each course, using a max-heap of durations to drop the longest course whenever the accumulated time exceeds the current deadline. The heap size is the answer.

Hint

Dropping the longest course when over time frees the most room for later ones.

Test cases

case 1

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

expected: 3

case 2

in: [[[1,2]]]

expected: 1

case 3

in: [[[3,2],[4,3]]]

expected: 0

case 4

in: [[]]

expected: 0

case 5

in: [[[1,2],[2,3],[3,4]]]

expected: 2

Starter codePython

def schedule_course_max(courses):
    # Your code here
    pass

5 test cases · run your code against them in the editor