553. Deadline Courses
A learner starts on day 0 and wants to complete as many self-paced courses as possible, one at a time with no overlap and no breaks mattering. Course i is given as courses[i] = [duration, lastDay]: it takes exactly duration consecutive days, and it must be finished on or before day lastDay. A course may be started the moment the previous one ends, and the order is up to the learner.
Return the maximum number of courses that can be completed. Courses that are skipped cost nothing. If no course fits, return 0.
An O(n log n) time solution using O(n) space is expected.
Example 1
- Input:
- courses = [[3,9],[2,5],[4,8],[6,12]]
- Output:
- 3
- Explanation:
Taking the courses with deadlines 5, 8 and 9 in that order finishes them on days 2, 6 and 9; adding the 6-day course would end on day 15, past its deadline of 12, so the best is 3.
Example 2
- Input:
- courses = [[2,3],[2,3]]
- Output:
- 1
- Explanation:
Either course alone fits by day 3, but together they end on day 4, so only 1 can be completed.
Example 3
- Input:
- courses = [[7,5]]
- Output:
- 0
- Explanation:
The only course takes 7 days but must end by day 5, so nothing can be completed.
Constraints
1 ≤ courses.length ≤ 100000courses[i].length == 21 ≤ duration ≤ 1041 ≤ lastDay ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)