630. 课程表 III

630. 课程表 III

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](auto& v1, auto& v2)
        {
            return v1[1] < v2[1];
        });
        priority_queue<int> pq;
        int endTime = 0;
        for(auto& course : courses)
        {
            if(endTime + course[0] <= course[1])
            {
                endTime += course[0];
                pq.push(course[0]);
            }
            else if(!pq.empty() && course[0] < pq.top()) // 重点在这，如果当前不能简单得加到原来的序列中，那么如果当前的消耗时间小于里面的最长时间，就替换进去
            {
                endTime -= pq.top();
                endTime += course[0];
                pq.pop();
                pq.push(course[0]);
            }
        }
        return pq.size();
    }
};

设之前的是t1 + t2 + .... t_j-1 + t_j + t_j+1 +.....tk <= dk

那么将t_j替换成t_i后，由于后者小于前者，所以上述关系仍旧存在，而由于d_i <= d_k，所以都成立。