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

简介: LeetCode-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 个请求的工作量(也就是服务器完成它所需要的时间)。你的任务是找到 最繁忙的服务器 。最繁忙定义为一个服务器处理的请求数是所有服务器里最多的。

请你返回包含所有 最繁忙服务器 序号的列表,你可以以任意顺序返回这个列表。

 

示例 1:

 

输入:k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]

输出:[1]

解释:

所有服务器一开始都是空闲的。

前 3 个请求分别由前 3 台服务器依次处理。

请求 3 进来的时候,服务器 0 被占据,所以它呗安排到下一台空闲的服务器,也就是服务器 1 。

请求 4 进来的时候,由于所有服务器都被占据,该请求被舍弃。

服务器 0 和 2 分别都处理了一个请求,服务器 1 处理了两个请求。所以服务器 1 是最忙的服务器。

示例 2:

输入:k = 3, arrival = [1,2,3,4], load = [1,2,1,2]

输出:[0]

解释:

前 3 个请求分别被前 3 个服务器处理。

请求 3 进来,由于服务器 0 空闲,它被服务器 0 处理。

服务器 0 处理了两个请求,服务器 1 和 2 分别处理了一个请求。所以服务器 0 是最忙的服务器。

示例 3:

输入:k = 3, arrival = [1,2,3], load = [10,12,11]

输出:[0,1,2]

解释:每个服务器分别处理了一个请求,所以它们都是最忙的服务器。

示例 4:

输入:k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]

输出:[1]

示例 5:

输入:k = 1, arrival = [1], load = [1]

输出:[0]

 

提示:

1 <= k <= 105

1 <= arrival.length, load.length <= 105

arrival.length == load.length

1 <= arrival[i], load[i] <= 109

arrival 保证 严格递增 。

 

解题思路

模拟题,利用一个set存储当前空闲的服务器,利用优先队列存储正在运行的服务器,每次新请求到达前,先更新忙碌服务器的状态,然后在空闲服务器中找出编号最小的大于等于i % k的服务器,执行请求,统计每个服务器处理的请求数目,然后返回最大值的下标。

代码展示

class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
        vector<int> viCount(k, 0);
        vector<int> viRet;
        set<int> setiAvailable;
        for (int i = 0; i < k; i++) {
            setiAvailable.insert(i);
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
        for(int i = 0; i < arrival.size(); i++)
        {
            while(!busy.empty())
            {
                auto p = busy.top();
                if(p.first <= arrival[i])
                {
                    busy.pop();
                    setiAvailable.insert(p.second);
                }   
                else
                    break;
            }
            if(setiAvailable.empty())
                continue;
            auto p = setiAvailable.lower_bound(i % k);
            if(p == setiAvailable.end())
                p = setiAvailable.begin();
            busy.emplace(arrival[i] + load[i], *p);
            viCount[*p]++;
            setiAvailable.erase(*p);
        }
        int iMax = 0;
        for(auto iter: viCount)
            iMax = max(iter, iMax);
        for(int i = 0; i < k; i++)
        {
            if(viCount[i] == iMax)
                viRet.push_back(i);
        }
        return viRet;
    }
};

运行结果

 

相关文章
|
4月前
|
Swift iOS开发
iOS Swift使用Alamofire请求本地服务器报错-1002
iOS Swift使用Alamofire请求本地服务器报错-1002
110 1
|
4月前
|
开发框架 缓存 .NET
并发请求太多,服务器崩溃了?试试使用 ASP.NET Core Web API 操作筛选器对请求进行限流
并发请求太多,服务器崩溃了?试试使用 ASP.NET Core Web API 操作筛选器对请求进行限流
217 0
|
2月前
|
JSON JavaScript 前端开发
《进阶篇第6章:vue中的ajax》包括回顾发送ajax请求方式、vue-cli脚手架配置代理服务器、vue-resource
《进阶篇第6章:vue中的ajax》包括回顾发送ajax请求方式、vue-cli脚手架配置代理服务器、vue-resource
59 22
|
2月前
|
前端开发 JavaScript Java
第6章:Vue中的ajax(包含:回顾发送ajax请求方式、vue-cli脚手架配置代理服务器)
第6章:Vue中的ajax(包含:回顾发送ajax请求方式、vue-cli脚手架配置代理服务器)
74 4
|
2月前
|
前端开发 Java
学习SpringMVC,建立连接,请求,响应 SpringBoot初学,如何前后端交互(后端版)?最简单的能通过网址访问的后端服务器代码举例
文章介绍了如何使用SpringBoot创建简单的后端服务器来处理HTTP请求,包括建立连接、编写Controller处理请求,并返回响应给前端或网址。
56 0
学习SpringMVC,建立连接,请求,响应 SpringBoot初学,如何前后端交互(后端版)?最简单的能通过网址访问的后端服务器代码举例
|
3月前
|
开发者
HTTP状态码是由网页服务器返回的三位数字响应代码,用于表示请求的处理结果和状态
HTTP状态码是由网页服务器返回的三位数字响应代码,用于表示请求的处理结果和状态
33 1
|
4月前
|
缓存 数据安全/隐私保护 UED
代理服务器在HTTP请求中的应用:Ruby实例
代理服务器在HTTP请求中的应用:Ruby实例
|
5月前
|
存储 运维 Java
函数计算产品使用问题之如何使用Python的requests库向HTTP服务器发送GET请求
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。
106 8
|
5月前
|
Shell Python
`pytest-httpserver`是一个pytest插件,它允许你在测试期间启动一个轻量级的HTTP服务器,并模拟HTTP请求和响应。
`pytest-httpserver`是一个pytest插件,它允许你在测试期间启动一个轻量级的HTTP服务器,并模拟HTTP请求和响应。
|
5月前
|
前端开发 JavaScript
【node写接口】 通过node 快速搭建一个服务器、get请求、post请求 小白入门
【node写接口】 通过node 快速搭建一个服务器、get请求、post请求 小白入门
154 4