华为4.13机试第二题工单调度策略

题目描述

当小区通信设备上报警时，系统会自动生成待处理的工单，工单调度系统需要根据不同的策略，调度外线工程师（FME）上站去修复工单对应的问题。

根据与运营商签订的合同，不同严重程度的工单被处理并修复的时长要求不同，这个要求被修复的时长我们称之为SLA时间。假设华为与运营商A签订了运维合同，部署了一套调度系统，只有1个外线工程师（FME），每个工单根据问题严重程度会给一个评分，在SLA时间内完成修复的工单，华为员工获得工单对应的积分，超过SLA完成的工单不获得积分，但必须完成该工单，运营商最终会根据积分付款。请设计一种调度策略，根据现状得到调度结果完成所有工单，让这个外线工程师处理的工单处理的工单获得的总积分最多。

假设从某个调度时刻开始，当前工单数量N，不会产生新的工单，每个工单处理修复耗时为1小时。请设计你的调度策略，完成业务目标。不考虑外线工程师在小区之间行驶的耗时。

输入描述

第一行为一个整数N，表示工单的数量。

接下来N行，每行包括两个整数，第一个整数表示工单的SLA时间（小时），第二个数表示工单的积分。

输出描述

输入一个可以获得的最大积分

输入样例：

假设有7个工单的SLA时间（小时）和积分如下：

第一行N为工单个数，接下来的N行为订单最小完成时间（在这个时间之前完成才有积分，可以不做）和积分；

输出：15

此题不能用贪心算法（按时间排序，每个时间取一个最大值），贪心遇到如下例子则错

贪心的输出为6与实际的10不符；

采用两个优先队列，一个存储已拿到积分的工单（q），另一个存储每个时间段中的最大积分工单（p，当然也可以直接从map中取，然后pop_back()末尾元素）

注意已拿到积分的工单数量在每个时间段不可以超过该时间段的值，即当前时间为4，队列q中最多4个工单；

随后每个时间段检查q的队首元素和p的队首元素大小，p大则弹出q的队首元素，将p的队首元素放入q；

#include <iostream>
#include <queue>
#include <map>
using namespace std;

int main() {
int n;
cin >> n;
int maxNum = 0;//工单中最大的完成时间，即每行第一个数字的最大值
int s1, s2;
map<int, vector<int>>_map;
int ans = 0;
for (int i = 0; i < n; ++i) {
cin >> s1 >> s2;
_map[s1].push_back(s2);
maxNum = max(maxNum, s1);
}
map<int, vector<int>>::iterator it = _map.begin();//存储工单，按照工单最小完成时间排序
priority_queue<int, vector<int>, greater<int>> q;//存储赚最大积分的工单
int count = 1;//count是当前所能做的最大工单数量
while (it != _map.end() && count<=maxNum) {
priority_queue <int, vector<int>, less<int>> p;//存储即将过期的工单(即如果当前时间为t，优先队列q中存储的工单数量是不可以大于q的)；
if (it->first == count) {
for (auto& s : it->second) {
p.push(s);
}
}
else {
count = it->first; continue;
}
int n = q.size();//当前存储的工单数量
while (n < count && p.size()) {
q.push(p.top());
ans += p.top(); p.pop();
++n;
}
while (q.size() <= maxNum && p.size()) {
if (p.top() > q.top()) {
ans += p.top() - q.top();
q.pop();
q.push(p.top());
p.pop();
}
else {
break;
}
}
++it; ++count;
}
cout << ans << endl;
}

#华为机试#