# Course Schedule III
**Difficulty:** HARD
[External](https://leetcode.com/problems/course-schedule-iii)
Canonical: https://scaleengineer.com/dsa/problems/course-schedule-iii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Works Applications](https://scaleengineer.com/companies/works-applications)
---
## Problem
There are `n` different online courses numbered from `1` to `n`. You are given an array `courses` where `courses[i] = [durationi, lastDayi]` indicate that the `ith` course should be taken **continuously** for `durationi` days and must be finished before or on `lastDayi`.

You will start on the `1st` 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 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th 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 <= 104`
* `1 <= durationi, lastDayi <= 104`

# Approaches
## Brute Force with Recursion
This approach explores all possible subsets of courses. For each subset, it checks if a valid schedule exists. A schedule is valid if all courses in it can be completed before their respective deadlines. This is the most straightforward but also the most inefficient method.
**Time:** O(2^N * N log N). There are 2^N subsets. For each subset of size `k`, sorting takes O(k log k) and validation takes O(k). In the worst case, this leads to a time complexity of O(2^N * N log N). · **Space:** O(N), where N is the number of courses. This space is used to store the current subset being evaluated and for the recursion stack if a recursive implementation is used.
**Pros:** Simple to conceptualize and understand.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method involves generating every possible combination of courses that can be taken. For each combination (a subset of the original courses), we must verify if it's possible to complete them all. A key insight is that if a set of courses can be completed, they can also be completed by taking them in increasing order of their deadlines (`lastDay`).

So, the algorithm is as follows: we generate all 2^N subsets of courses. For each subset, we sort it by `lastDay` and then simulate the process of taking them one by one. We keep a running `currentTime`. If we can complete all courses in the subset without violating any deadline, we compare its size with our current maximum and update it if necessary. This process is repeated for all subsets to find the largest valid one.
### Algorithm
- Generate all 2^N subsets of the given courses.
- For each subset:
  - Check if it's a valid set of courses to take.
    - To do this, sort the courses in the subset by their `lastDay`.
    - Iterate through the sorted courses, keeping track of the current total time.
    - If at any point `currentTime + duration > lastDay`, the subset is invalid.
  - If the subset is valid, update the maximum number of courses seen so far.
- Return the maximum count.

## Dynamic Programming
This approach uses dynamic programming to build the solution iteratively. By sorting the courses by their deadlines first, we can define a DP state that represents the minimum time to finish a certain number of courses. This is significantly better than brute force but not optimal.
**Time:** O(N^2). Sorting takes O(N log N). The nested loops for the DP calculation take O(N*N). The total complexity is dominated by O(N^2). · **Space:** O(N) for the `dp` array.
**Pros:** Much more efficient than the brute-force approach.; Provides a structured way to solve the problem based on optimal substructure.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N <= 10^4) and will likely result in a 'Time Limit Exceeded' error.
### Explanation
First, we sort the courses by their `lastDay`. This greedy step is crucial as it allows us to process courses in an order that simplifies dependencies. We define `dp[j]` as the minimum total time required to complete `j` courses. Our goal is to find the maximum `j` for which `dp[j]` is a finite value.

We initialize a `dp` array of size `n+1`, with `dp[0] = 0` and all other elements as infinity. We then iterate through each course `c = [duration, lastDay]` from the sorted list. For each course, we try to use it to update our `dp` array. Specifically, we check if taking this course can give us a better (smaller) finish time for taking `j` courses. If we take the current course as our `j`-th course, the finish time would be `dp[j-1] + duration`. This is a valid option only if this finish time does not exceed the course's deadline, `lastDay`. To ensure each course is considered only once for each count `j`, we iterate the inner loop for `j` backwards. After processing all courses, the answer is the largest `j` for which `dp[j]` is not infinity.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        int n = courses.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int[] course : courses) {
            int duration = course[0];
            int lastDay = course[1];
            for (int j = n; j >= 1; j--) {
                if (dp[j - 1] != Integer.MAX_VALUE) {
                    if (dp[j - 1] + duration <= lastDay) {
                        dp[j] = Math.min(dp[j], dp[j - 1] + duration);
                    }
                }
            }
        }

        for (int i = n; i >= 0; i--) {
            if (dp[i] != Integer.MAX_VALUE) {
                return i;
            }
        }
        return 0;
    }
}
```
### Algorithm
- Sort the `courses` array based on `lastDay` in ascending order.
- Initialize a `dp` array of size `n + 1`. Set `dp[0] = 0` and `dp[1...n]` to a large value representing infinity.
- For each course `[duration, lastDay]` in the sorted list:
  - For `j` from `n` down to `1`:
    - Calculate the potential finish time if this course is the `j`-th one: `finishTime = dp[j-1] + duration`.
    - If `dp[j-1]` is not infinity and `finishTime <= lastDay`:
      - Update `dp[j] = min(dp[j], finishTime)`.
- Find the largest index `ans` such that `dp[ans]` is not infinity.
- Return `ans`.

## Greedy Approach with Priority Queue
This is the most efficient approach, employing a greedy strategy. We process courses sorted by their deadlines. We tentatively take each course if possible. If taking a course violates its deadline, we check if we can swap it with a previously taken course that has a longer duration. This swap reduces the total time spent, potentially allowing us to take more courses overall.
**Time:** O(N log N). Sorting takes O(N log N). The loop runs N times, and each priority queue operation (offer, poll, peek) takes O(log K) time, where K is the number of courses taken so far (K <= N). This results in a total time complexity of O(N log N). · **Space:** O(N) in the worst case, where the priority queue might store the durations of all N courses.
**Pros:** Optimal time complexity that passes for the given constraints.; Elegant solution combining sorting and a priority queue.
**Cons:** The greedy logic, specifically the swapping step, might not be immediately obvious to come up with.
### Explanation
The optimal strategy involves a greedy choice. First, we sort the courses by their `lastDay`. This ensures we prioritize courses that need to be finished earlier. We iterate through these sorted courses, maintaining a `currentTime` which tracks the total duration of courses taken so far.

For each course, we check if we can add it to our schedule. If `currentTime + course.duration <= course.lastDay`, it fits perfectly. We add its duration to `currentTime` and add the duration to a max-priority queue. The priority queue will store the durations of all the courses we've decided to take.

If the course doesn't fit (`currentTime + course.duration > course.lastDay`), we have a conflict. We can't simply add it. However, we can check if it's beneficial to swap this current course with one we've already taken. To make the schedule more flexible for future courses, we want to minimize the `currentTime`. This can be achieved by replacing the longest course taken so far with the current course, but only if the current course is shorter. We use the max-priority queue to find the longest course taken so far (its `peek()`). If `pq.peek() > course.duration`, we perform the swap: remove the max duration from `pq` and `currentTime`, and add the current course's duration instead. This reduces the total time and makes the schedule valid for the current course, while keeping the number of courses taken the same.

After iterating through all courses, the size of the priority queue gives the maximum number of courses we could take.

```java
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));
        
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        int currentTime = 0;
        
        for (int[] course : courses) {
            int duration = course[0];
            int lastDay = course[1];
            
            if (currentTime + duration <= lastDay) {
                currentTime += duration;
                pq.offer(duration);
            } else if (!pq.isEmpty() && pq.peek() > duration) {
                currentTime += duration - pq.poll();
                pq.offer(duration);
            }
        }
        
        return pq.size();
    }
}
```
### Algorithm
- Sort the `courses` array based on `lastDay` in ascending order.
- Initialize a max-priority queue, `pq`, to store the durations of courses taken.
- Initialize `currentTime = 0`.
- For each course `[duration, lastDay]` in the sorted list:
  - If `currentTime + duration <= lastDay`:
    - Add the course: `currentTime += duration`, `pq.offer(duration)`.
  - Else if the priority queue is not empty and its top element (max duration) is greater than the current `duration`:
    - Swap the courses: `currentTime = currentTime - pq.poll() + duration`, `pq.offer(duration)`.
- Return the size of the priority queue.

# Solutions
### Java

```java
public class Course_Schedule_III { // https://leetcode.com/articles/course-schedule-iii/ public class Solution { public int scheduleCourse ( int [][] courses ) { Arrays . sort ( courses , ( a , b ) -> a [ 1 ] - b [ 1 ]); PriorityQueue < Integer > queue = new PriorityQueue <>(( a , b ) -> b - a ); // duration time放入heap int time = 0 ; for ( int [] c: courses ) { if ( time + c [ 0 ] <= c [ 1 ]) { queue . offer ( c [ 0 ]); time += c [ 0 ]; } else if (! queue . isEmpty () && queue . peek () > c [ 0 ]) { time += c [ 0 ] - queue . poll (); queue . offer ( c [ 0 ]); } } return queue . size (); } } } ############ class Solution { public int scheduleCourse ( int [][] courses ) { Arrays . sort ( courses , Comparator . comparingInt ( a -> a [ 1 ])); PriorityQueue < Integer > pq = new PriorityQueue <>(( a , b ) -> b - a ); int s = 0 ; for ( int [] course : courses ) { int duration = course [ 0 ], lastDay = course [ 1 ]; pq . offer ( duration ); s += duration ; if ( s > lastDay ) { s -= pq . poll (); } } return pq . size (); } }
```

### Python

```python
# idea: # sort all courses by deadline # iterate all sorted courses # if current course is able to be taken, then take it # if not, check if we can remove some courses from courses we already taken # if the one has the maximal duration is greater than current course's duration # then replace it by current course # since courses are already sorted by deadline, then our new deadline must be later # (why? because sorted by deadline, current deadline must be later than all deadlines of taken courses, # so it must be valid) # moreover, we have more available time for taking more courses class Solution ( object ): def scheduleCourse ( self , courses ): """ :type courses: List[List[int]] :rtype: int """ now = 0 heap = [] for t , d in sorted ( courses , key = lambda x : x [ 1 ]): if now + t <= d : now += t heapq . heappush ( heap , - t ) elif heap and - heap [ 0 ] > t : # here popped is already negative when being pushed now += t + heapq . heappop ( heap ) heapq . heappush ( heap , - t ) return len ( heap ) ############ class Solution : def scheduleCourse ( self , courses : List [ List [ int ]]) -> int : courses . sort ( key = lambda x : x [ 1 ]) pq = [] s = 0 for d , e in courses : heappush ( pq , - d ) s += d if s > e : s += heappop ( pq ) return len ( pq )
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/course-schedule-iii/ // Time: O(NT) // Space: O(NT) class Solution { vector < vector < int >> memo ; int dp ( vector < vector < int >> & A , int i , int time ) { if ( i == A . size ()) return 0 ; if ( memo [ i ][ time ] != - 1 ) return memo [ i ][ time ]; int pick = 0 ; if ( time + A [ i ][ 0 ] <= A [ i ][ 1 ]) pick = 1 + dp ( A , i + 1 , time + A [ i ][ 0 ]); int skip = dp ( A , i + 1 , time ); return memo [ i ][ time ] = max ( pick , skip ); } public: int scheduleCourse ( vector < vector < int >>& A ) { sort ( begin ( A ), end ( A ), []( auto & a , auto & b ) { return a [ 1 ] < b [ 1 ]; }); memo . assign ( A . size (), vector < int > ( A . back ()[ 1 ] + 1 , - 1 )); return dp ( A , 0 , 0 ); } };
```