题目描述
某工程师为了解决服务器负载过高的问题,决定使用多个服务器来分担请求消息。
现给定 k 台服务器(编号从 1 到 k),以及一批请求消息的信息,格式为到达时刻 负载大小,消息说明:
每个时刻最多只有一条消息到达;
负载大小表示服务器处理该消息所需时长。
请计算在负载分担规则下,哪些服务器处理的负载最高(服务器处理的负载为所处理的所有消息的负载累加和),并以升序返回这些服务器的编号。
负载分担规则:
按顺序循环分配服务器,如:有3台服务器且都空闲,分配的方式为 1->2->3->1… ;
如果某台服务器繁忙,则跳过该服务器;
如果一条消息到达时所有服务器繁忙,则丢弃这条消息。
解答要求
时间限制:1000ms, 内存限制:512MB
输入
第一行为服务器的个数 k,k 的范围 [1, 50000]
第二行为请求消息个数 n,n 的范围 [1, 50000]
随后的 n 行为各条消息的到达时刻和负载大小(注意并非按到达时刻升序给出)。
消息到达时刻的范围 [1, 10^9],负载大小的范围 [1, 10^9]
输出
处理负载最多的服务器编号,注意按升序输出。
样例
输入样例 1
3
7
1 15
2 10
12 10
5 10
6 10
30 15
32 10
输出样例 1
1 3
提示样例 1
根据输入信息,经过分析可得以下表:
到达时刻 | 消息负载 | 完成时刻(不包含) | 分配服务器号 |
---|---|---|---|
1 | 15 | 16 | 1 |
2 | 10 | 12 | 2 |
5 | 10 | 15 | 3 |
6 | 10 | 16 | 丢弃 |
12 | 10 | 22 | 2 |
30 | 15 | 45 | 3 |
32 | 10 | 42 | 1 |
根据上表分析,1和3号服务器处理的负载都为25,按照升序排列,输出的结果为:1 3
Java算法源码
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
// 待实现函数,在此函数中填入答题代码
static int[] findHighestLoadServers(int serverNum, Message[] messages) {
boolean[] isBusy = new boolean[serverNum]; // 下标为server编号-1,值为是否忙碌
int[