一、題目描述

給定n臺(tái)主機(jī)（編號(hào)1~n）和某批數(shù)據(jù)包，數(shù)據(jù)包格式為（抵達(dá)主機(jī)時(shí)刻，負(fù)載量）。這里數(shù)據(jù)每個(gè)時(shí)刻最多只有1條數(shù)據(jù)到達(dá)。負(fù)載量表示該主機(jī)處理此數(shù)據(jù)包總耗時(shí)。請(qǐng)計(jì)算輪詢負(fù)載均衡規(guī)則下，哪些主機(jī)負(fù)載最高（即處理數(shù)據(jù)的負(fù)載量總和），升序輸出主機(jī)編號(hào)。

二、說明

輪詢負(fù)載均衡規(guī)則：如果3臺(tái)主機(jī)均空閑，分配方案為1，2，3，1，2…。如果某主機(jī)繁忙，則跳過該主機(jī)；如果某條數(shù)據(jù)到達(dá)時(shí)所有主機(jī)均繁忙，則丟棄這條數(shù)據(jù)。

三、舉例

輸入
3
1 15
2 10
12 10
5 10
6 10
30 15
32 10
輸出
1 3

四、算法

public int[] findHighestHost(int serverNum, Message[] messages) {Arrays.sort(messages, Comparator.comparingInt(m -> m.time));// times[i]表示第i臺(tái)主機(jī)，下次可處理請(qǐng)求的時(shí)刻int[] times = new int[serverNum];// 初始值設(shè)置為1Arrays.fill(times, 1);// load[i]表示第i臺(tái)主機(jī)的負(fù)載值int[] loads = new int[serverNum];// 輪詢主機(jī)索引，從第1臺(tái)主機(jī)開始int start = 0;for (Message message : messages) {boolean flag = false;int j = 0;for (int i = 0; i < serverNum; i++) {j = (start + i) % serverNum;if (times[j] <= message.time) {// 當(dāng)前主機(jī)j下次可以處理請(qǐng)求的時(shí)刻值 <= 當(dāng)前消息時(shí)刻值，滿足處理?xiàng)l件times[j] = message.time + message.load;loads[j] += message.load;flag = true;// 找到滿足條件的主機(jī)編號(hào)j后，直接跳出當(dāng)前for循環(huán)，輪詢尋找下次消息處理的主機(jī)編號(hào)break;}}// 輪詢尋找下次主機(jī)編號(hào)if (flag) {start = (j + 1) % serverNum;}}// 找出最大負(fù)載結(jié)果List<Integer> ans = new ArrayList<>();ans.add(0);for (int i = 0; i < serverNum; i++) {if (loads[i] > loads[ans.get(0)]) {ans.clear();ans.add(i);} else if (loads[i] == loads[ans.get(0)]) {ans.add(i);}}// 由于主機(jī)編號(hào)從1開始，而ans中值從0開始，所以這里需要自增1return ans.stream().mapToInt(i -> i + 1).toArray();}static class Message {int time;int load;}