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] = [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

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();
    }
};