Loading page…
Practice problem · hard
An exam-prep portal offers short courses. Each course needs a number of study days, and it must be finished by a last day. A student studies one course at a time, with no breaks, starting on day 0, and may skip any course.
A course that needs 3 days and starts on day 0 finishes on day 3. It is on time when its finish day is at most its last day. You get the list of courses, and you find the most courses the student can finish on time.
Write most_courses(courses).
courses[i] = [days, last_day], with days >= 1.Input: courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3Sort by last day. Add each course to the plan, and add its days to the total. If the total passes the course's last day, drop the longest course in the plan.
| Course | Days total after adding | On time? | Action | Courses in plan |
|---|---|---|---|---|
| [100, 200] | 100 | yes | keep | 1 |
| [1000, 1250] | 1100 | yes | keep | 2 |
| [200, 1300] | 1300 | yes | keep | 3 |
| [2000, 3200] | 3300 | no, 3300 > 3200 | drop the longest, 2000 | 3 |
The answer is 3.
Input: courses = [[3, 2]]
Output: 0The only course needs 3 days, so it finishes on day 3, after its last day of 2.
Input: courses = [[1, 2], [2, 3]]
Output: 2Study the first course on day 0 to 1, then the second on day 1 to 3. Both are on time.
0 ≤ courses.length ≤ 100,0001 ≤ days, last_day ≤ 1,000,000Trying every subset of courses means 2^n subsets, which is impossible even for n = 60. You need a sort, which costs n log n, and a heap, whose operations each cost log n.
most_courses · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.