LeetCode 630: Course Schedule III

Problem Description

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

You will start on the 1^st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation:
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1^st course, it costs 100 days so you will finish it on the 100^th day, and ready to take the next course on the 101^st day.
Second, take the 3^rd course, it costs 1000 days so you will finish it on the 1100^th day, and ready to take the next course on the 1101^st day.
Third, take the 2^nd course, it costs 200 days so you will finish it on the 1300^th day.
The 4^th course cannot be taken now, since you will finish it on the 3300^th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

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

Constraints:

1 <= courses.length <= 10⁴
1 <= duration_i, lastDay_i <= 10⁴

Difficulty: Hard

Tags: array, greedy, sorting, heap (priority queue)

Rating: 97.43%

Intuition

This problem can be solved using a greedy approach combined with a max heap. The key insights are:

Sort courses by their deadlines (lastDay) to process them in order of urgency
Keep track of total time spent on courses
Use a max heap to store the durations of taken courses
When we can’t fit a new course, try replacing the longest course we’ve taken if it would help

Solution

Here’s my Python solution to this problem:

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

        total_time = 0
        taken = [] # max heap to store durations of taken courses

        for duration, lastDay in courses:
            # Check if we can take this course within the deadline
            if total_time + duration <= lastDay:
                total_time += duration
                heappush(taken, -duration)  # negative for max heap
            # If we can't take it direclty, try replacing the longest course
            elif taken and -taken[0] > duration:
                longest = -heappop(taken)
                total_time = total_time - longest + duration
                heappush(taken, -duration)
        
        return len(taken)

Detailed Example Walkthrough

Let’s walk through the example: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]

First, sort by deadline:

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

Process each course:
- Course 1: [100,200]
  - Time: 0 + 100 = 100 ≤ 200
  - Heap: [-100]
  - Can take it ✅
- Course 2: [1000,1250]
  - Time: 100 + 1000 = 1100 ≤ 1250
  - Heap: [-1000, -100]
  - Can take it ✅
- Course 3: [200,1300]
  - Time: 1100 + 200 = 1300 ≤ 1300
  - Heap: [-1000, -200, -100]
  - Can take it ✅
- Course 4: [2000,3200]
  - Time: 1300 + 2000 = 3300 > 3200
  - Current longest course: 1000
  - Even replacing won’t help: 2300 + 2000 > 3200
  - Cannot take it ❌

Final result: 3 courses can be taken.

Complexity Analysis

Time Complexity: $O(n logn)$
- Sorting takes $O(n log n)$
- Heap operations take $O(log k)$ where k is heap size
Space Complexity: $O(n)$
- We store at most n courses in the heap

Key Insights

Sorting by deadline is crucial as it ensures we process courses in order of urgency
Using a max heap allows us to efficiently track and replace the longest course when needed
The greedy approach works because:
- We always try to take courses if possible
- When we can’t take a course, we only replace if it improves our situation
- We always replace the longest course if needed