## Problem

**Problem ID**: 630

**Title**: Course Schedule III

**Difficulty**: Hard

**Description**:

There are `n`

different online courses numbered from `1`

to `n`

. You are given an array `courses`

where `courses[i] = [duration`

indicate that the _{i}, lastDay_{i}]`i`

course should be taken ^{th}**continuously** for `duration`

days and must be finished before or on _{i}`lastDay`

._{i}

You will start on the `1`

day and you cannot take two or more courses simultaneously.^{st}

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`

^{4}`1 <= duration`

_{i}, lastDay_{i}<= 10^{4}

## Thoughts

I found this problem very difficult. I tunnel visioned into the solving this problem using the typical interval + greedy method. However, as each course is not fixed, that approach will not work. I had to look at the solution to solve this problem

## Solution

**General Idea**

- The key observation you have to make is:
- Given a list of selected courses we can replace the selected course with a better course (same end but shorter duration)

- In the optimal solution we will schedule all the courses back to back without any gaps in time in between them.
- Sort the courses in ascending order of their ending duration and keep track of the next available time
- Iterate through the sorted course:
- If the current course can be schedule (current time + duration < end time) then we will add the course duration into the priority queue and advance the time
- Else if the current course is shorter than the largest course duration in the priority queue.
- This means that we would replace the largest previous schedule with the current schedule

### Implementation

```
class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(), [](const auto& a, const auto& b) { return a[1] < b[1];});
priority_queue<int> pq;
int time = 1;
for (const auto course : courses) {
if (course[1] - course[0] + 1 >= time) {
time += course[0];
pq.push(course[0]);
} else if (!pq.empty() && course[0] < pq.top()) {
time += (course[0] - pq.top());
pq.pop();
pq.push(course[0]);
}
}
return pq.size();
}
};
```