C++ 13 lines With Explanation


  • 8
    B

    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.


  • 0
    J

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


  • 0
    B

    @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.


  • 0

    Nice solution


  • 0
    J

    @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?


  • 0
    B

    @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.


  • 0
    L

    Great solution. Thanks a lot.


  • 0
    Z

    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!


  • 0
    B

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


  • 0
    Z

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


  • 0
    N
    This post is deleted!

  • 0
    B

    @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.


  • 0
    Z

    @baselRus Great! Thanks!


  • 0
    A

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

  • 0
    T
    This post is deleted!

  • 0
    B

    @baselRus said in C++ 13 lines With Explanation:

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

Log in to reply
 

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