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

一、题目描述

给定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];
// 初始值设置为1
Arrays.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开始，所以这里需要自增1
return ans.stream().mapToInt(i -> i + 1).toArray();
}
static class Message {
int time;
int load;
}