Course4all
Join us on telegram
Home/dsa/Greedy/Course Schedule III

Course Schedule III

Master this topic with zero to advance depth.

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();
    }
}
← Previous QuestionWeighted Job Scheduling
Next Question →Two City Scheduling