传送门 LeeCode 1606. 找到处理最多请求的服务器
模拟请求的过程，暴力 O ( n 2 ) O(n^2) O(n2)，需要优化每个请求选择服务器的算法。设服务器 j j j 执行上一个任务需要执行到 l a s t [ j ] last[j] last[j]，那么第 i i i 次请求需要求解满足 l a s t [ j ] ≤ a r r i v a l [ i ] last[j]\leq arrival[i] last[j]≤arrival[i] 的所有服务器的最小索引，优先考虑区间 [ i % k , k ) [i\%k,k) [i%k,k)，再考虑 [ 0 , i % k ) [0,i\%k) [0,i%k)。
考虑到 a r r i v a l [ i ] arrival[i] arrival[i] 单调递增，那么前一个请求开始时已完成前一个任务的服务器，在下一个请求到来前也必然已完成前一个任务（不包括当前任务），那么用优先队列维护正在执行任务的服务器 l a s t [ i ] last[i] last[i]，每次请求到来将满足条件的服务器出队；用 s e t set set 维护空闲的服务器，按优先级二分查找最小索引。
class Solution { typedef pair<int, int> P; public: vector<int> busiestServers(int k, vector<int> &arrival, vector<int> &load) { set<int> st; for (int i = 0; i < k; i++) { st.insert(i); } vector<int> cnt(k); priority_queue<P, vector<P>, greater<P>> q; int n = arrival.size(); for (int i = 0; i < n; i++) { while (!q.empty() && q.top().first <= arrival[i]) { P p = q.top(); q.pop(); st.insert(p.second); } set<int>::iterator ite; if ((ite = st.lower_bound(i % k)) != st.end()) { ++cnt[*ite]; q.push(P(arrival[i] + load[i], *ite)); st.erase(ite); } else if ((ite = st.lower_bound(0)) != st.end()) { ++cnt[*ite]; q.push(P(arrival[i] + load[i], *ite)); st.erase(ite); } } vector<int> res; int mx = *max_element(cnt.begin(), cnt.end()); for (int i = 0; i < k; i++) { if (cnt[i] == mx) { res.push_back(i); } } return res; } };