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