每日一题-找到最多请求的服务器

发表于 分类于 Waline：

1606. 找到处理最多请求的服务器

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-servers-that-handled-most-number-of-requests

题目

你有 k 个服务器，编号为 0 到 k-1 ，它们可以同时处理多个请求组。每个服务器有无穷的计算能力但是 不能同时处理超过一个请求 。请求分配到服务器的规则如下：

  • 第 i （序号从 0 开始）个请求到达。
  • 如果所有服务器都已被占据，那么该请求被舍弃（完全不处理）。
  • 如果第 (i % k) 个服务器空闲，那么对应服务器会处理该请求。
  • 否则，将请求安排给下一个空闲的服务器（服务器构成一个环，必要的话可能从第 0 个服务器开始继续找下一个空闲的服务器）。比方说，如果第 i 个服务器在忙，那么会查看第 (i+1) 个服务器，第 (i+2) 个服务器等等。 给你一个 严格递增 的正整数数组 arrival ，表示第 i 个任务的到达时间，和另一个数组 load ，其中 load[i] 表示第 i 个请求的工作量（也就是服务器完成它所需要的时间）。你的任务是找到 最繁忙的服务器 。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。请你返回包含所有 最繁忙服务器 序号的列表，你可以以任意顺序返回这个列表。

思路

首先每次任务来的时候对当前正在运行任务的服务器进行判断，将已经完成的服务器放回可使用的服务器列表里。如果每次任务来都对运行中服务器遍历查询，复杂度可达$O(n^2)$，可以用堆进行优化，每次只要判断堆顶的（最早完成的）服务器是否完成即可，优化至$O(nlogn)$。对于空闲的处理器，由于使用它们时是有顺序的，如果使用数组保存每次都要遍历整个服务器列表，不可取。使用有序数据结构进行保存，既set红黑树。注意首先需要判断i%k开始的服务器，利用二分查找进行定位时使用set自带的lower_bound进行查找，凡事数据结构有自己的搜索函数一律用该数据结构特有的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class cmp {
	public:
	    bool operator()(const vector<int> &a, const vector<int> &b) {
		// 结束时间早的排在堆顶
		return a[1] > b[1];
	}
}
;
class Solution {
	public:
	    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
		int n = arrival.size();
		set<int> spqre;
		priority_queue<vector<int>,vector<vector<int>>,cmp> busy;
		vector<int> reqs(k,0);
		for (int i = 0 ; i < k ; ++i) {
			spqre.insert(i);
			// 初始全部空闲
		}
		for (int i = 0 ; i < n ; ++i) {
			while (!busy.empty() && busy.top()[1] <= arrival[i]) {
				// 把完成任务的处理器移动至spqre
				int j = busy.top()[0];
				busy.pop();
				spqre.insert(j);
			}
			auto it = spqre.lower_bound(i%k);
			if (it == spqre.end()) {
				it = spqre.begin();
			}
			if (it == spqre.end()) {
				continue;
			}
			int j = *it;
			reqs[j]++;
			busy.push( {
				j,arrival[i]+load[i]
			}
			);
			spqre.erase(j);
		}
		int maxReqs = *max_element(reqs.begin(),reqs.end());
		vector<int> ans;
		for (int i = 0 ; i < k ; ++i) {
			if (reqs[i] == maxReqs) {
				ans.push_back(i);
			}
		}
		return ans;
	}
}
;