Course Schedule III

HardHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

There are n online courses. courses[i] = [duration_i, lastDay_i] means course i takes duration_i consecutive days and must be **finished no later than** day lastDay_i. You start on day 1 and can take only one course at a time, back to back. A course taking d days started right after finishing at day t finishes at day t + d. Each course can be taken at most once, and you may skip any course. Return the **maximum number** of courses you can complete.

Examples

Input: courses = [[3,4],[2,5],[4,9],[5,9]]
Output: 3
Take durations 3, 2, and 4, finishing on days 3, 5, and 9. All four courses together need 14 days, which misses the last deadline.
Input: courses = [[5,3],[2,2]]
Output: 1
The 2-day course fits by day 2. The 5-day course can never finish by day 3.
Input: courses = [[4,3]]
Output: 0
The only course takes longer than its deadline allows.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems