LeetCode 630 - Course Schedule III

LeetCode Problem 630

Difficulty: 🔴 Hard
Topics: Array, Greedy, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives a list of online courses, where each course is represented as [duration, lastDay].

The duration tells us how many consecutive days are required to complete the course. The lastDay tells us the latest possible day by which the course must be finished.

You begin on day 1, and only one course can be taken at a time. Once you start a course, you must complete it continuously before moving on to another course.

The goal is to determine the maximum number of courses that can be completed without violating any deadlines.

In other words, we want to carefully choose and order courses so that:

• The total elapsed time never exceeds the deadline of any course being completed.
• The number of selected courses is as large as possible.

The constraints are important:

• Up to 10^4 courses
• Each duration and deadline can also be up to 10^4

A brute-force solution that tries every subset or every ordering is infeasible because the number of combinations grows exponentially.

A few important observations immediately stand out:

• Some courses are impossible to take individually, for example a course [5,3] because it already exceeds its own deadline.
• Taking a long course early may block several smaller courses later.
• The order of courses matters significantly.
• Greedy decisions are necessary because the input size is large.

Important edge cases include:

• A single impossible course
• Multiple courses sharing the same deadline
• Very large duration courses that should be skipped
• Cases where replacing one previously chosen course with a shorter one enables more total courses
• Inputs where the optimal schedule is not the same as sorting by shortest duration

Approaches

Brute Force Approach

A brute-force solution would try all possible subsets of courses and determine whether each subset can be scheduled feasibly.

One possible strategy is:

1. Generate every subset of courses.
2. For each subset, try every possible ordering.
3. Simulate taking the courses one by one.
4. Check whether all deadlines are satisfied.
5. Track the maximum valid subset size.

This works because it explores every possible valid schedule and therefore guarantees the optimal answer.

However, the complexity is enormous.

For n courses:

• There are 2^n subsets.
• Each subset may require permutation checks.
• Even optimized pruning remains exponential.

With n = 10^4, this is completely impractical.

Key Insight for the Optimal Solution

The critical observation is that deadlines naturally suggest a greedy ordering.

If we process courses in increasing order of deadline:

• Earlier deadlines are more restrictive.
• If we can satisfy early deadlines first, we preserve flexibility for later courses.

However, simply taking every course greedily does not always work.

Suppose adding a course causes the total time to exceed the current deadline. In that situation, we need to decide which course should be removed.

To maximize the number of courses taken, we should remove the course with the largest duration.

Why?

Because removing the longest course frees the maximum amount of time while sacrificing only one course.

This leads directly to a greedy + max heap strategy:

• Sort courses by deadline.
• Keep track of selected course durations in a max heap.
• Maintain the current total time.
• If total time exceeds the current deadline, remove the longest course taken so far.

This ensures we always maintain the most time-efficient set of courses.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all subsets and orderings
Optimal	O(n log n)	O(n)	Greedy scheduling with max heap

Algorithm Walkthrough

1. Sort all courses by their lastDay in ascending order.

This ensures we always process the most urgent deadlines first. If a course has an earlier deadline, it must be considered before later-deadline courses. 2. Initialize a variable total_time = 0.

This keeps track of how many days are currently occupied by selected courses. 3. Initialize a max heap.

The heap stores durations of selected courses. Since Python's heapq is a min heap, we store negative durations to simulate a max heap. 4. Iterate through the sorted courses one by one.

For each course:

• Add its duration to total_time
• Push the duration into the heap

At this point, we tentatively assume we will take the course. 5. Check whether the current schedule violates the deadline.

If total_time > lastDay, the schedule is no longer feasible. 6. Remove the longest course taken so far.

Pop the maximum duration from the heap and subtract it from total_time.

This is the greedy optimization step. Removing the longest course frees the most time and maximizes our chance of fitting future courses. 7. Continue processing all courses.

The heap always contains the durations of the currently selected feasible set of courses. 8. Return the heap size.

The number of elements in the heap equals the maximum number of courses that can be completed.

Why it works

The algorithm maintains an important invariant:

At every step, the selected set of courses is the feasible set with the minimum possible total duration among all sets of the same size.

When a deadline violation occurs, removing the longest course is always optimal because it reduces total time the most while keeping as many courses as possible.

Sorting by deadline ensures that once we satisfy all earlier deadlines, future decisions only need to consider maintaining feasibility for later deadlines.

This greedy replacement strategy guarantees the maximum number of courses.

Python Solution

from typing import List
import heapq

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        # Sort by deadline
        courses.sort(key=lambda course: course[1])

        total_time = 0

        # Max heap implemented using negative values
        max_heap = []

        for duration, last_day in courses:
            total_time += duration
            heapq.heappush(max_heap, -duration)

            # If schedule becomes invalid,
            # remove the longest course
            if total_time > last_day:
                longest_duration = -heapq.heappop(max_heap)
                total_time -= longest_duration

        return len(max_heap)

The implementation begins by sorting the courses according to their deadlines. This guarantees that courses with tighter constraints are handled first.

The variable total_time stores the cumulative duration of all currently selected courses.

The heap stores durations of selected courses. Since Python only provides a min heap, negative values are inserted so the largest duration appears first when popped.

For every course:

• The algorithm tentatively includes it.
• The total time increases.
• The course duration is added to the heap.

If the deadline becomes violated, the longest course is removed immediately. This may remove the newly added course or some previously selected longer course.

At the end, the heap contains exactly the courses that can be completed while maximizing the count.

Go Solution

package main

import (
	"container/heap"
	"sort"
)

type MaxHeap []int

func (h MaxHeap) Len() int {
	return len(h)
}

func (h MaxHeap) Less(i, j int) bool {
	return h[i] > h[j]
}

func (h MaxHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func scheduleCourse(courses [][]int) int {
	sort.Slice(courses, func(i, j int) bool {
		return courses[i][1] < courses[j][1]
	})

	totalTime := 0
	maxHeap := &MaxHeap{}
	heap.Init(maxHeap)

	for _, course := range courses {
		duration := course[0]
		lastDay := course[1]

		totalTime += duration
		heap.Push(maxHeap, duration)

		if totalTime > lastDay {
			longest := heap.Pop(maxHeap).(int)
			totalTime -= longest
		}
	}

	return maxHeap.Len()
}

The Go implementation uses the container/heap package to build a custom max heap.

Unlike Python, Go does not require negating values because the comparison behavior can be customized through the Less method.

Slices are used naturally for heap storage, and integer overflow is not a concern because the maximum cumulative duration remains within reasonable bounds for Go's integer type.

Worked Examples

Example 1

Input:

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

After sorting by deadline:

[[100,200],[1000,1250],[200,1300],[2000,3200]]

Step	Course	Total Time	Heap Contents	Action
1	[100,200]	100	[100]	Add
2	[1000,1250]	1100	[1000,100]	Add
3	[200,1300]	1300	[1000,100,200]	Add
4	[2000,3200]	3300	[2000,1000,200,100]	Exceeds deadline
5	Remove longest	1300	[1000,200,100]	Remove 2000

Final heap size is 3.

Answer:

3

Example 2

Input:

courses = [[1,2]]

Step	Course	Total Time	Heap	Action
1	[1,2]	1	[1]	Add

Final answer:

1

Example 3

Input:

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

Sorted order remains the same.

Step	Course	Total Time	Heap	Action
1	[3,2]	3	[3]	Exceeds deadline
2	Remove 3	0	[]	Remove
3	[4,3]	4	[4]	Exceeds deadline
4	Remove 4	0	[]	Remove

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting plus heap operations
Space	O(n)	Heap may store all selected courses

The sorting step requires O(n log n) time.

Each course is pushed into the heap once and possibly removed once. Heap operations take O(log n) time, so all heap operations together also require O(n log n).

The heap may contain up to n courses in the worst case, so the space complexity is O(n).

Test Cases

from typing import List

class Solution:
    def scheduleCourse(self, courses: List[List[int]]) -> int:
        import heapq

        courses.sort(key=lambda x: x[1])

        total_time = 0
        max_heap = []

        for duration, last_day in courses:
            total_time += duration
            heapq.heappush(max_heap, -duration)

            if total_time > last_day:
                total_time += heapq.heappop(max_heap)

        return len(max_heap)

solution = Solution()

assert solution.scheduleCourse([[100,200],[200,1300],[1000,1250],[2000,3200]]) == 3  # provided example
assert solution.scheduleCourse([[1,2]]) == 1  # single valid course
assert solution.scheduleCourse([[3,2],[4,3]]) == 0  # no valid courses
assert solution.scheduleCourse([[5,5],[4,6],[2,6]]) == 2  # replacement optimization
assert solution.scheduleCourse([[1,3],[2,4],[3,5]]) == 2  # cannot fit all courses
assert solution.scheduleCourse([[5,10],[2,5],[3,7]]) == 2  # sorting by deadline matters
assert solution.scheduleCourse([[1,2],[2,3],[3,4]]) == 1  # tight deadlines
assert solution.scheduleCourse([[100,200],[50,100],[25,50]]) == 3  # all courses fit
assert solution.scheduleCourse([[10,5]]) == 0  # individually impossible course
assert solution.scheduleCourse([[1,10000]] * 1000) == 1000  # large repeated input

Test Case Summary

Test	Why
[[100,200],[200,1300],[1000,1250],[2000,3200]]	Validates the main greedy replacement logic
[[1,2]]	Smallest valid input
[[3,2],[4,3]]	No course can be scheduled
[[5,5],[4,6],[2,6]]	Confirms longest-course removal behavior
[[1,3],[2,4],[3,5]]	Tests overlapping deadlines
[[5,10],[2,5],[3,7]]	Ensures deadline sorting matters
[[1,2],[2,3],[3,4]]	Tight constraints reduce schedule size
[[100,200],[50,100],[25,50]]	All courses fit successfully
[[10,5]]	Single impossible course
[[1,10000]] * 1000	Stress test for performance and heap behavior

Edge Cases

One important edge case occurs when a course cannot satisfy its own deadline, such as [10,5]. A naive implementation might incorrectly include it temporarily and fail to remove it properly. In this solution, the course is added first, then immediately removed because the total time exceeds the deadline. This naturally handles impossible courses without special-case logic.

Another critical edge case involves courses with the same deadline but different durations. For example, [[5,10],[2,10],[3,10]]. A naive greedy strategy might choose the first course encountered and miss the opportunity to take more shorter courses. The heap-based replacement strategy guarantees that the longest durations are discarded first, preserving the maximum course count.

A third important case happens when adding a new short course should replace a previously selected long course. Consider [[5,5],[4,6],[2,6]]. If we greedily keep the earlier long course, we can only complete one course. The optimal algorithm replaces the longer duration with the shorter one, enabling more total courses to fit within deadlines.

Another subtle edge case is when all courses fit exactly at their deadlines. The algorithm correctly allows equality because the condition only removes a course when total_time > lastDay, not when they are equal. This ensures valid schedules are preserved.