Leetcode 630: Course Schedule III

https://leetcode.com/problems/course-schedule-iii/description/

Notes:

This question is quick tricky.

One way to solve this problem is to sort the input by the ending time, which is like a deadline.

In general, we wish to choose classes with a shorter duration and a later deadline.

For the classes with the same deadline, we would to choose firstly the one with the shortest duration.

One variable is also needed to represent the current ending time: cur_time.

If cur_time + duration[i] <= deadline[i], we just need to place  duration[i] into a set;

otherwise, if duration[i] < *set.rbegin() (the last element in set), we just need to replace the last element by duration[i].

Why does this greedy way work?

1): since duration[i] is shorter (and the deadline may be later as well), thus it is definitely a better choice than *set.rbegin().

2): if we choose duration[i], we cannot choose *set.rbegin(), since the sum time is beyond the deadline;

3): so we have to choose one of them, which is duration[i].

Now is the key, can we simply place duration[i] into the set without checking its validity?

The answer is Yes. Before duration[i]，all the elements inside the set satisfy the constrain: sum time <= deadline. Now after the switch, the sum time becomes smaller, and the deadline becomes no smaller. So the constrain still hold automatically. And it is still the optimal solution.

In one word, once we meet with a solution with a shorter duration and a later deadline, and it cannot fit in with the current sum time, we need to replace the longest duration one already chosen by the new one with a shorter duration.

See the code below:

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(begin(courses), end(courses), [](auto &a, auto &b) {return a[1] < b[1];});
        multiset<int> st;
        int time = 0;
        for(int i=0; i<courses.size(); ++i) {
            if(time + courses[i][0] <= courses[i][1]) {
                st.insert(courses[i][0]);
                time += courses[i][0];
            }
            else {
                if(st.size() && *st.rbegin() > courses[i][0]) {
                    time += courses[i][0] - *st.rbegin();
                    st.erase(--st.end());
                    st.insert(courses[i][0]);
                }
            }
        }
        return st.size();
    }
};

The code can be simplified further using a priority_queue.

See the code below:

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