Skip to main content

630 - Course Schedule III

Difficulty: Hard | Pattern: Greedy + Max-Heap | Company tags: Google, Amazon

Problem Statement​

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicates that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day. Return the maximum number of courses that you can take.

Example 1:

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

Approach: Sort by Deadline + Max-Heap — O(n log n)​

Key insight: Sort by deadline. Take each course greedily. If adding a course exceeds its deadline, replace the longest course taken so far (if it's longer) — this frees up time without reducing count.

import heapq

def scheduleCourse(courses: list[list[int]]) -> int:
    courses.sort(key=lambda x: x[1])  # sort by deadline
    
    max_heap = []  # stores durations (negated for max-heap)
    time = 0
    
    for duration, last_day in courses:
        if time + duration <= last_day:
            heapq.heappush(max_heap, -duration)
            time += duration
        elif max_heap and -max_heap[0] > duration:
            # Replace longest course with current shorter course
            time += duration + max_heap[0]  # max_heap[0] is negative
            heapq.heapreplace(max_heap, -duration)
    
    return len(max_heap)

Dry Run​

courses = [[100,200],[200,1300],[1000,1250],[2000,3200]] (already sorted by deadline)

coursetimeactionheap
[100,200]0+100=100 lte 200take[-100]
[200,1300]100+200=300 lte 1300take[-200,-100]
[1000,1250]300+1000=1300 gt 1250200 gt 1000? No[-200,-100]
[2000,3200]300+2000=2300 lte 3200take[-2000,-200,-100]

Result: len(heap) = 3 ✓

Why Sort by Deadline?​

A course with an earlier deadline must be completed first. Otherwise we might take a long course that prevents us from meeting an earlier deadline for a short course.

Complexity​

  • Time: O(n log n)
  • Space: O(n)