HardArrayGreedyHeap (Priority Queue)Sorting

Course Schedule III

1 approach, code in every language

You are given a list of online courses, where each course is described by two integers: the number of days it takes to finish and the last day by which it must be completed. Specifically course i is written as [duration_i, lastDay_i], meaning it occupies duration_i consecutive days and has to be finished on or before day lastDay_i.

You start on the first day and can take at most one course at a time; courses are taken one after another with no overlap. A course counts as completed only if it finishes on or before its deadline.

Return the maximum number of courses you can complete under these rules.

Example 1

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

Output: 3

Taking the first three courses in a feasible order finishes them within their deadlines; the last course cannot fit, so the answer is three.

Example 2

Input: courses = [[3,2],[4,3]]

Output: 0

Neither course can finish by its deadline, since the first needs 3 days but is due on day 2, so no courses are completed.

Constraints

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

Greedy by Deadline with a Max-Heap of Durations

Process courses by increasing deadline and evict the longest chosen course whenever elapsed time overflows.

Loading animation…

Intuition

Sorting by deadline lets us consider courses in the order their windows close, which is the order in which commitments become urgent. We optimistically take every course and accumulate the elapsed time so far. Whenever the running time passes the current course's deadline, at least one previously chosen course must be dropped, and dropping the one with the largest duration frees the most time while removing only a single course. A max-heap keeps the largest taken duration at hand for instant eviction, and because each eviction removes exactly one course, the final heap size is the maximum number of courses that fit.

Algorithm walkthrough

1Sort the courses in non-decreasing order of their last allowed day.
2Iterate through the sorted courses, adding each duration to a running total of consumed days and pushing that duration onto a max-heap.
3If the running total now exceeds the current course's deadline, pop the largest duration from the heap and subtract it from the total.
4This keeps the selected set feasible while never reducing its size below the best achievable so far.
5After processing every course, the number of elements remaining in the heap is the answer.

Implementation

import heapq
from typing import List

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        heap = []  # max-heap via negated durations
        time = 0
        for duration, last_day in courses:
            time += duration
            heapq.heappush(heap, -duration)
            if time > last_day:
                time += heapq.heappop(heap)  # popped value is negative
        return len(heap)

Time

O(n log n)

Space

O(n)

Sorting dominates; each course is pushed onto and popped from the heap at most once.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free