Skip to main content
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...