【优先级队列】任务分配

任务分配问题，有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; }