Description

给定一个数组$a[1,n]$，每个元素$a_i$具有2种属性$\{d_i,l_i\}$，其中$d_i$表示消耗时长，$l_i$表示最后期限（含）。每单位时长只能同时消费$1$个元素。求最多能消耗的元素个数

Constraints

• $1\le n\le {10}^4$
• $1\le d_i,l_i\le {10}^4$

Solution

这道题适合作为反悔贪心的第二题。关联：第一题

数组按$l_i$排序，大根堆按$d_i$排序。这样保证了堆内操作时任意元素都是合法的

维护$sum$表示总时长，每次$sum+d_i$不超过则加入，否则淘汰$sum$内耗时最长的，等效替换为当前元素的$d_i$

Code

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        ranges::sort(courses, [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        priority_queue<int> pq;
        int sum = 0;
        for(auto &c : courses) {
            if(sum + c[0] <= c[1]) {
                pq.emplace(c[0]);
                sum += c[0];
            } else if(!pq.empty()) {
                auto d = pq.top();
                if(c[0] < d && sum - d + c[0] <= c[1]) {
                    pq.pop();
                    pq.emplace(c[0]);
                    sum -= d;
                    sum += c[0];
                }
            }
        }
        return pq.size();
    }
};

Link

LeetCode-630 Course Schedule III