Course4all

Course Schedule III

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

Course Schedule III

Take maximum number of courses given [duration, lastDay] constraints.

Visual Representation

Courses: [[100, 200], [1000, 1250], [200, 1300]] 1. [100, 200] -> time=100. Heap: [100]. 2. [1000, 1250] -> time=1100. Heap: [100, 1000]. 3. [200, 1300] -> time=1300. Heap: [100, 200, 1000]. Result: 3
Hard

Examples

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Take course 1, 3, and 2.
Approach 1

Level I: Recursive Backtracking

Intuition

Try all possible subsets of courses. For each subset, check if there exists an ordering that satisfies all deadlines. The maximum subset size that works is the answer.

Thought Process

  1. Generate all 2N2^N subsets of courses.
  2. For each subset, sort it by deadline and check if it's feasible.
  3. Return the maximum feasible subset size.

Pattern: Brute Force / Subsets

⏱ O(2^N * N log N).💾 O(N)

Detailed Dry Run

[[100,200], [1000, 1250], [200, 1300]]
  • Try subset [[100,200], [200,1300]]: Feasible? 100<=200 (Y), 300<=1300 (Y). Size 2.
  • Try subset [[100,200], [1000,1250], [200,1300]]: Feasible? 100<=200, 1100<=1250, 1300<=1300. YES. Size 3.
java
// Brute Force Code: Exponential O(2^N)
// Try every subset and check feasibility after sorting by deadline.
Approach 2

Level II: Dynamic Programming

Intuition

This can be viewed as an 0/1 Knapsack problem where the 'weight' is the duration and the 'limit' is the deadline. We sort by deadline first to ensure we process courses in an order that respects feasibility.

Thought Process

  1. Sort courses by lastDay.
  2. dp[i][t] = max courses among first i that can be finished by time t.
  3. This is still too slow (N⋅MaxDayN \cdot MaxDay). A better DP is dp[i][j] = min time to finish j courses using first i courses.

Pattern: Dynamic Programming

⏱ O(N^2).💾 O(N^2) or O(N).

Detailed Dry Run

Sorted: [[100,200], [200, 1300]] dp[0][0]=0, dp[0][1]=100 (others inf) dp[1][0]=0, dp[1][1]=min(100, 200)=100, dp[1][2]=100+200=300 (300<=1300? Yes)
java
public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        int n = courses.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        int max = 0;
        for (int[] c : courses) {
            for (int j = max; j >= 0; j--) {
                if (dp[j] + c[0] <= c[1]) {
                    dp[j + 1] = Math.min(dp[j + 1], dp[j] + c[0]);
                    max = Math.max(max, j + 1);
                }
            }
        }
        return max;
    }
}
Approach 3

Level III: Optimal Greedy (Max-Heap + Retroactive Swap)

Intuition

Process courses by deadline. If a course doesn't fit, replace the longest course already taken with this shorter one to save time.

Thought Process

  1. Sort by lastDay.
  2. Maintain time and a Max-Heap of durations.
  3. Add current duration to time and heap.
  4. If time > lastDay, subtract the max duration from time (pop heap).

Pattern: Greedy with Retroactive Swap

⏱ O(N log N).💾 O(N).

Detailed Dry Run

[[100, 200], [500, 600], [200, 600]]
  1. [100, 200]: time=100, heap=[100]
  2. [500, 600]: time=600, heap=[500, 100]
  3. [200, 600]: time=800 > 600. Pop 500. time=300, heap=[200, 100] Result: 2
java
public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int time = 0;
        for (int[] c : courses) {
            time += c[0]; pq.add(c[0]);
            if (time > c[1]) time -= pq.poll();
        }
        return pq.size();
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionWeighted Job Scheduling
Next Question →Two City Scheduling