口碑好的网站开发浙江坤宇建设有限公司 网站

任务分配问题，有n个任务，每个任务有个达到时间。将这些任务分配给m个处理器，进行处理。每个处理器的处理时间不一样。处理器的任务列表有最大任务数限制。
分配任务的策略是：当前待分配的任务的处理时刻最小。如果处理时刻相同，处理器id小的优先。
假设从时刻0开始分配任务和处理任务。在某一时刻，要求处理器先标记任务的完成状态，再接受新的任务。
问所有问题处理完毕后的时刻是多少？

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <string>
#include <queue>
using namespace std;class Solution
{
public:int Dispatch(vector<int> timeUnit, vector<int> arriveTimeList, int queueLen){int n = timeUnit.size();this->timeUnit = timeUnit;this->queueLen = queueLen;taskTime.resize(n, 0);taskCount.resize(n, 0);auto cmp = [&] (int x, int y) -> bool {if (taskCount[x] == queueLen && taskCount[y] == queueLen) {return x > y;}if (taskCount[x] == queueLen) {return true;}if (taskCount[y] == queueLen) {return false;}int time1 = taskTime[x] + timeUnit[x] * taskCount[x];int time2 = taskTime[y] + timeUnit[y] * taskCount[y];if (time1 == time2) {return x > y;}return time1 > time2;};int j = 0;int curTime = 0;for (; ; curTime++) {priority_queue<int, vector<int>, function<bool(int,int)>> q(cmp);// 出队for (int i = 0; i < n; i++) {if (taskCount[i] == 0) {q.push(i);continue;}int cnt = (curTime - taskTime[i]) / timeUnit[i];taskCount[i] -= cnt;if (taskCount[i] < 0) {taskCount[i] = 0;taskTime[i] = 0;} else {taskTime[i] += cnt * timeUnit[i];}q.push(i);}int task = q.top();// 入队，直到不能再加了while (j < arriveTimeList.size() && arriveTimeList[j] <= curTime && taskCount[task] < queueLen) {q.pop();taskCount[task]++;if (taskCount[task] == 1) {taskTime[task] = curTime;}j++;q.push(task);task = q.top();}if (j == arriveTimeList.size()) {break;}}int ans = 0;for (int i = 0; i < n; i++) {ans = max(ans, taskTime[i] + taskCount[i] * timeUnit[i]);}return ans;}
private:vector<int> taskTime;vector<int> taskCount;vector<int> timeUnit;int queueLen;
};int main(int argc, char *argv[])
{vector<int> timeUnit = {1, 2, 3, 4, 5};vector<int> arriveTimeList = {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7};int rightAns = 5;Solution s;int ans = s.Dispatch(timeUnit, arriveTimeList, 3);cout << "ans: " << ans << endl;return 0;
}