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

LeetCode-630 Course Schedule III