一、题意

有n个工作（n<=800000），只能串行进行，已知每个工作的用时need[i]和截止期限ddl[i]，问最多能完成多少个工作？

二、解析

这个是超典型的工作安排贪心问题。

一个比较简单的版本是给出工作的确切开始时间和结束时间，这种问题就是典型的区间限制问题，我们按照ddl排序，然后先完成ddl早的任务即可。

但是在这道题中，任务的开始时间是可以任意决定的（只要结束时不超过ddl期限），因此我们还应该结合考虑另一种贪心：即让短的任务优先。

也就是说，对于一个给定的时间点之前，我们需要先执行短的任务，这样才能让任务完成数量最大化。这里需要用一个优先队列来存放到当前时间点为止，所有已经选择的任务。用这个优先队列的目的是为了能获得已经选择的任务中用时最长的那一个，这样就能在当发现一个任务由于超时无法选择时可以有尝试替换的机会（即从之前选择的任务中挑一个用时长的取消掉，从而使得当前任务不会超时）。

这样就巧妙地实现了在给定时间点之前的短任务优先。更详细的实现细节可以见代码。

三、代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 800000 + 5;
struct task {
    int need, ddl;
    task(int need, int ddl) : need(need), ddl(ddl) {}
    bool operator < (const task& rhs) const {
        return ddl < rhs.ddl;
    }
};
int kase, n;

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        vector<task> vec;
        while(n --) {
            int q, d;
            cin >> q >> d;
            vec.push_back(task(q, d));
        }
        sort(vec.begin(), vec.end());

        priority_queue<int> que;
        int cur = 0;
        for(const task& t : vec) {  // 总体上还是优先考虑ddl早的任务
            if(cur + t.need <= t.ddl) {
                cur += t.need;
                que.push(t.need);
            }
            else if(!que.empty() && que.top() > t.need) {  // 反正都会有一个任务不能完成，不如留下用时短的任务（当前任务）
                cur += t.need - que.top();                 // 即用这个ddl更晚的但用时更短的task替换一个ddl早一些但是用时长的task
                que.pop();                                 // 由于当前任务的ddl更晚，用时也更短，因此替换后必然不会超时
                que.push(t.need);
            }
        }
        cout << que.size() << endl;
        if(kase) cout << endl;
    }
}

四、归纳

  • 任务安排的贪心问题：按照ddl来逐个考虑，以实现优先考虑ddl早的任务；同时利用优先队列来维护已选择的任务中耗时最多的，以备替换，以实现在给定时间点之前短任务优先。