中國(guó)做網(wǎng)站的公司有哪些磁力天堂
一、題目描述
給定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;}