Compile Ready
Module 6 · Heap + Greedy

Course Schedule III

HardProblem 16 of 21 10 min read ~30 min to solve LeetCode
GreedyHeapPriority QueueSortingScheduling
Asked atGoogleAmazonMicrosoftMetaApple

Problem Statement

You are given an array courses where courses[i] = [duration, lastDay]. Course i takes duration days and must be completed on or before lastDay. You start on day 0 and can take only one course at a time. Return the maximum number of courses you can finish.

Input

A 2D integer array courses, where each row gives a course duration and its last valid completion day.

Output

An integer: the maximum number of courses that can be completed before their deadlines.

Constraints

  • •1 <= courses.length <= 10^4
  • •1 <= duration, lastDay <= 10^4

Examples

Example 1

Input: 
courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation: Take the 100-day, 1000-day, and 200-day courses. The 2000-day course is too costly to keep once it pushes total time past day 3200.

Example 2

Input: 
courses = [[1,2]]
Output: 1
Explanation: The only course finishes on day 1, which is before its deadline day 2.

Example 3

Input: 
courses = [[3,2],[4,3]]
Output: 0
Explanation: Each course individually takes longer than its deadline, so no course can be completed.

Learning Objectives

  • Recognise when a greedy schedule needs the ability to undo a previous choice.
  • Sort deadline-constrained jobs by deadline and maintain the best feasible prefix.
  • Use a max-heap to remove the longest selected duration when the schedule becomes infeasible.
  • Explain the exchange argument behind replacing a long course with a shorter one.

Intuition

The greedy insight is to process courses in the order their deadlines become urgent. After considering all courses with deadline up to some day, we want the largest possible set whose total duration fits by that day.

The difficult part is that taking a course early may later become a bad commitment. A heap fixes that. We tentatively take every course, then if the total time exceeds the current deadline, we remove the longest course taken so far. Removing the longest duration gives back the most time while losing only one course, so it is the safest possible repair.

This is not the naive rule take the shortest available course or take courses by deadline only. The heap lets the algorithm revise earlier choices while preserving the best count for every deadline prefix.

Common mistakes

  • ×Sorting by duration instead of deadline, which ignores when courses expire.
  • ×Rejecting only the current course when the schedule overflows, even if an earlier longer course is the real problem.
  • ×Using a min-heap for durations, which removes the cheapest course and keeps the schedule unnecessarily long.
  • ×Checking feasibility only at the end instead of after each deadline prefix.

Algorithm Explanation

Greedy strategy

Sort courses by lastDay. Walk through that order, tentatively add each duration to the schedule, and store selected durations in a max-heap. If the running total exceeds the current course deadline, remove the largest duration from the heap.

Why it works

After processing courses up to a particular deadline, all selected courses must fit within that deadline. If the total is too large, any feasible solution with the same number of selected courses must drop at least one selected course. Dropping the longest selected course leaves the smallest possible total time among all one-course removals, so it preserves the best chance to keep the same count for later deadlines.

Proof of correctness

Consider the courses in sorted deadline order. Maintain the invariant that after each step, the heap contains the maximum number of courses possible from the processed prefix, and among schedules with that count, its total duration is as small as possible. Adding a new course can only increase the count by one. If the total still fits, the invariant remains true. If the total exceeds the current deadline, every feasible schedule from this prefix with the tentative count must remove one selected course. Exchanging out the longest selected duration for any shorter removal cannot increase total time, so removing the longest gives a schedule no worse than any other one-removal repair. The count drops by exactly one, which is unavoidable. Therefore the invariant holds for every prefix, and after the last prefix the heap size is the maximum number of courses.

Algorithm

  1. Sort courses by increasing lastDay.
  2. Keep totalTime as the sum of selected durations and a max-heap of selected durations.
  3. For each course, add its duration to totalTime and the heap.
  4. If totalTime exceeds the current deadline, poll the heap and subtract that longest duration.
  5. Return the heap size.

Solutions

Solution: Deadline order with max-heap replacement

Sort by deadline so every overflow is detected at the earliest point it matters. The max-heap stores the durations we currently plan to take. Whenever the prefix becomes infeasible, remove the longest selected duration because it frees the most time while sacrificing only one course.

Step-by-step

  1. Sort the input by lastDay in ascending order.
  2. Initialise totalTime = 0 and an empty max-heap of durations.
  3. For each course, tentatively take it by adding its duration to the heap and to totalTime.
  4. If totalTime is greater than this course deadline, remove the heap maximum and subtract it from totalTime.
  5. The remaining heap entries are the courses in the best feasible schedule, so return the heap size.
Time

O(n log n)

Space

O(n)

Sorting costs O(n log n), and each course is pushed once and popped at most once from the heap.

Java implementation

Loading…

Dry Run

Sample input

courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]. After sorting by deadline: [100,200], [1000,1250], [200,1300], [2000,3200].

coursedeadlineactiontotal timemax-heap durationsanswer so far
[100,200]200take 100100[100]1
[1000,1250]1250take 10001100[1000,100]2
[200,1300]1300take 2001300[1000,200,100]3
[2000,3200]3200take 2000, overflow, remove 20001300[1000,200,100]3

The last course is tentatively added, but keeping it would finish at day 3300, beyond deadline 3200. Removing the longest selected duration restores total time to 1300 while keeping 3 courses.

Interview Tips

Lead with the deadline-prefix invariant. The interviewer wants to hear that once courses are sorted by deadline, every processed prefix has a single feasibility condition: selected total time must fit by the current deadline. The max-heap is the rollback mechanism that removes the worst duration whenever that condition breaks.

Likely follow-ups

  • How would the solution change if each course had a profit and you wanted maximum profit instead of maximum count?
  • What if courses also had release dates before which they could not start?
  • Can you recover one actual set of scheduled course indices, not just the count?
  • Why does removing the longest selected course beat removing the newly added course every time?

Similar Problems

Furthest Building You Can Reach
MediumAlso uses a heap to revise which expensive choices get premium resources.
IPO
HardUses heaps to choose the best available candidate as constraints evolve.
Maximum Number of Events That Can Be Attended
MediumAnother scheduling problem where deadline order drives the greedy choice.
Task Scheduler
MediumA heap-based scheduling pattern with constraints over time.

Key Takeaways

  • Sort by the constraint that expires first: the course deadline.
  • When a chosen set becomes infeasible, remove the selected item with the worst duration cost.
  • A max-heap gives greedy algorithms a controlled undo operation.
  • The invariant is maximum count with minimum total duration for every processed deadline prefix.
Reusable template: Deadline-prefix greedy with rollback: sort by deadline, tentatively accept candidates, and use a max-heap to discard the most expensive selected item whenever feasibility breaks.