Back to ChallengesCourse Schedule IIIHard 55 min

Course Schedule III

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [duration_i, lastDay_i] indicate that the ith course should be taken continuously for duration_i days and must be finished before or on lastDay_i.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Examples

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]

Output: 3

Take the 1st, 2nd, and 3rd courses for a total duration of 1300.

Constraints

• 1 <= courses.length <= 10^4
• 1 <= duration_i, lastDay_i <= 10^4

Complexity Analysis

Time

O(N log N) using a true Priority Queue (the array sort approach is O(N^2)).

Space

O(N)

storing selected durations.

Test Cases

#1 Standard case

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]

Expected: 3

#2 Single course

Input: courses = [[1,2]]

Expected: 1

Output

Click "Run Code" to see output here...