# C++ 13 lines With Explanation

• First, we sort courses by the end date, this way, when we're iterating through the courses, we can switch out any previous course with the current one without worrying about end date.

Next, we iterate through each course, if we have enough days, we'll add it to our multiset. If we don't have enough days, then we can either ignore this course, or we can use it to replace a longer course we added earlier.

``````class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
// sort courses by the end date
sort(courses.begin(),courses.end(),
[](vector<int> a, vector<int> b){return a.back()<b.back();});

multiset<int> cls; // store lengths of each course we take (could be duplicates!)
int cursum=0;

for (int i=0; i<courses.size(); i++) {

// if we have enough time, we will take this course
if (cursum+courses[i].front()<=courses[i].back()) {
cls.insert(courses[i].front());
cursum+=courses[i].front();
} else if (*cls.rbegin()>courses[i].front()) {
// if we don't have enough time, we switch out a longer course
cursum+=courses[i].front()-*cls.rbegin();
cls.erase(--cls.end());
cls.insert(courses[i].front());
} // if we don't have enough time for course[i],
//and it's longer than any courses taken, then we ignore it
}

return cls.size();
}
};
``````

My final consideration was when we replace a longer course with a much shorter one, does that mean we'll have enough room to take some courses previously ignored for being too long?

The answer is no, because any courses we missed would be longer than what's in multiset `cls`. So the increase in number of days cannot be larger than the largest element in `cls`, and certainly will be less than a previously ignored course which has to be even longer.

• Is it guaranteed that removing only one course (the largest one seen so far) will give us enough days to take courses[i]?

• @jamarshon Yes, we're only replacing a longer course (last element of multiset `cls` with `courses[i]`, we're not adding an additional course here.

• Nice solution

• @baselRus sorry I meant that is there a case where even taking out the largest course isn't enough? for example after you take out the longest course and you somehow find that you still need more days to cover courses[i] so you have to take out another course?

• @jamarshon In that case, we'll ignore the longer course. We will only do a replacement if it allows us to shorten the total amount of time we spend in all our courses. I'll add this implicit consideration into my explanation, thanks.

• Great solution. Thanks a lot.

• Hi
I have a question.
mt.erase(*mt.rbegin()); At this line, if i use *mt.rbegin(), not --mt.end() . I would fail at some testcase(not everyone). Do you know the reason? Thanks!

• @zmyzz `multiset.erase()` can only take as input `multiset<int>::iterator`, it cannot take as input `multiset<int>::reverse_iterator` - such as `rbegin()`.

• @baselRus Yes, But i add *, which change it into a value? Correct? And it only fails some case, not everyone.

• This post is deleted!

• @zmyzz Sorry, I missed the `*`. Yes, that would allow you to delete the value from the `multiset`. However, you would be deleting all elements of the same value, which is not what you want to do while trying to replacing courses one by one.

• @baselRus Great! Thanks!

• It will be faster if you use call by reference during sorting.

``````        // sort courses by the end date
sort(courses.begin(),courses.end(),
[](vector<int> &a, vector<int> &b){return a.back()<b.back();});
``````

• This post is deleted!

• you can use priority queue to avoid using iterator / pointer which is error-prone

``````class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses) {
sort(courses.begin(), courses.end(),
[](vector<int>&v1, vector<int>&v2){return v1.back() < v2.back();});
priority_queue<int>pq;
int curTime = 0;
for(auto & e : courses)
{
if(curTime + e[0] <= e[1])
{
curTime += e[0];
pq.push(e[0]);
}
else if(e[0] < pq.top())
{
curTime += e[0] - pq.top();
pq.pop();
pq.push(e[0]);
}
}
return pq.size();
}
};``````

• It is pretty good solution, thanks!

``````            else if (*cls.rbegin()>courses[i].front()) {
// if we don't have enough time, we switch out a longer course
cursum+=courses[i].front()-*cls.rbegin();
cls.erase(--cls.end());
cls.insert(courses[i].front());
} // if we don't have enough time for course[i],
//and it's longer than any courses taken, then we ignore it
``````

is

``````            else{
cls.insert(t);
auto it = --cls.end();
time += t - (*it);
cls.erase(it);
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.