作业调度
进阶作业调度利用截止时间和利润做贪心，优先保住高利润任务。
// 算法讲解
作业调度
输入偶数个整数：截止时间、利润交替。
待机
速度 中
待机 ⌨1int jobSchedule(vector<tuple<int,int,int>>& jobs) {
2 sort(jobs.begin(), jobs.end(),
3 [](auto& a, auto& b) { return get<2>(a) > get<2>(b); });
4 int maxDeadline = 0;
5 for (auto& j : jobs) maxDeadline = max(maxDeadline, get<1>(j));
6 vector<int> slot(maxDeadline + 1, -1);
7 int profit = 0;
8 for (auto& [id, dead, p] : jobs) {
9 for (int t = dead; t >= 1; t--) {
10 if (slot[t] == -1) { slot[t] = id; profit += p; break; }
11 }
12 }
13 return profit;
14}
复杂度分析
时间 O(n log n)
空间 O(n)
最优 O(n)
最坏 O(n log n)
算法讲解
每个作业有一个截止时间和利润，同一时间只能做一个作业，目标是使总利润最大。
贪心策略是按利润从大到小排序，依次把作业安排在其截止时间之前最晚的空闲槽位。
如果截止时间之前所有槽位都被占用，就放弃这个作业。
并查集可以用来加速空闲槽位的查找，把时间复杂度降到接近 O(n)。