【轮询负载均衡规则算法设计题】

一、题目描述

给定n台主机（编号1~n）和某批数据包，数据包格式为（抵达主机时刻，负载量）。这里数据每个时刻最多只有1条数据到达。负载量表示该主机处理此数据包总耗时。请计算轮询负载均衡规则下，哪些主机负载最高（即处理数据的负载量总和），升序输出主机编号。

二、说明

轮询负载均衡规则：如果3台主机均空闲，分配方案为1，2，3，1，2…。如果某主机繁忙，则跳过该主机；如果某条数据到达时所有主机均繁忙，则丢弃这条数据。

三、举例

输入
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台主机，下次可处理请求的时刻int[] times = new int[serverNum];// 初始值设置为1Arrays.fill(times, 1);// load[i]表示第i台主机的负载值int[] loads = new int[serverNum];// 轮询主机索引，从第1台主机开始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) {// 当前主机j下次可以处理请求的时刻值 <= 当前消息时刻值，满足处理条件times[j] = message.time + message.load;loads[j] += message.load;flag = true;// 找到满足条件的主机编号j后，直接跳出当前for循环，轮询寻找下次消息处理的主机编号break;}}// 轮询寻找下次主机编号if (flag) {start = (j + 1) % serverNum;}}// 找出最大负载结果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);}}// 由于主机编号从1开始，而ans中值从0开始，所以这里需要自增1return ans.stream().mapToInt(i -> i + 1).toArray();}static class Message {int time;int load;}