vlambda博客
学习文章列表

题目描述

写在前面： 最近在忙毕设的事情，笔记耽搁的很久，慢慢补。
本题目来自 LeetCode 上的 『1606. 找到处理最多请求的服务器』
由于题目描述过于复杂，直接点击查看原文转到原题目那里吧。

题解

有序集合+优先队列
题目要求优先选编号最小的空闲服务器，考虑使用有序集合set<int> free；将编号和处理结束时间放入优先队列busy中；使用数组cnts记录每个服务器处理的请求数目。
假设当前的请求为第 个，处理过程如下：

1. 如果当前 busy不为空，则判断队首对应服务是否小于等于当前请求到达时间，如果是，则弹出队首，并将对应服务器放到空闲列表 free中，直到不满足条件。
2. 如果 free为空，则表示所有服务器都在忙，丢弃当前请求。
3. 如果 free不为空，查找其中大于等于 的最小元素，如果找不到则使用第一个元素，将其作为响应服务器处理该请求。
4. 将找到的服务器编号和当前请求处理结束时间加入队列中
5. 重复1-4，直到所有请求都处理完毕。
6. 遍历 cnts，得到处理请求最多的服务器。

#define PII pair<int, int>
class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        set<int> free;
        priority_queue<PII, vector<PII>, greater<>> busy;
        vector<int> cnts(k, 0);
        int maxElement = 0;
        for (int i = 0; i < k; ++i) {
            free.emplace(i);
        }
        int n = arrival.size();
        for (int i = 0; i < n; ++i) {
            while (!busy.empty() && busy.top().first <= arrival[i]) {
                free.emplace(busy.top().second);
                busy.pop();
            }
            if (free.empty()) {
                continue;
            }
            auto p = free.lower_bound(i % k);
            p = p == free.end() ? free.begin() : p;
            ++cnts[*p];
            maxElement = max(maxElement, cnts[*p]);
            busy.emplace(arrival[i] + load[i], *p);
            free.erase(p);
        }
        // int maxElement = *max_element(cnts.begin(), cnts.end());
        vector<int> ans;
        for (int i = 0; i < k; ++i) {
            if (cnts[i] == maxElement) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

• 时间复杂度
• 空间复杂度