Find Servers That Handled Most Number of Requests LeetCode solution in Java

1
class Solution {
2
  public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
3

4
    // use a tree to track available servers
5
    TreeSet<Integer> availableServerIdxs = new TreeSet<Integer>();
6
    for (int num = 0; num < k; num++) {
7
      availableServerIdxs.add(num);
8
    }
9
    // use a PQ to maintain the availability based on curTime + loadTime and the server index =
10
    // idx%k
11
    Queue<int[]> runningServers = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
12

13
    int[] serverHandledReqCount = new int[k];
14

15
    for (int idx = 0; idx < arrival.length; idx++) {
16
      int newTaskCompletionTime = arrival[idx];
17

18
      // peek if the server's work time is less than or equal to the next task completion time, if
19
      // it is poll those servers from the running servers queue and add the index of that server to
20
      // the availableServerIdxs treeSet
21
      while (!runningServers.isEmpty() && runningServers.peek()[0] <= newTaskCompletionTime) {
22
        int freedServer = runningServers.poll()[1];
23
        availableServerIdxs.add(freedServer);
24
      }
25

26
      if (availableServerIdxs.size() == 0) continue; // all busy
27

28
      // to always get the last freed server
29
      Integer serverIdx = availableServerIdxs.ceiling(idx % k);
30

31
      if (serverIdx == null) {
32
        serverIdx = availableServerIdxs.first();
33
      }
34

35
      serverHandledReqCount[serverIdx]++;
36
      availableServerIdxs.remove(serverIdx);
37

38
      runningServers.offer(new int[] {newTaskCompletionTime + load[idx], serverIdx});
39
    }
40

41
    int max = Arrays.stream(serverHandledReqCount).max().getAsInt();
42
    return IntStream.range(0, k)
43
        .filter(i -> serverHandledReqCount[i] == max)
44
        .boxed()
45
        .collect(Collectors.toList());
46

47
    // return findMaxesInCounter(counter);
48
  }
49

50
  /*
51
  private List<Integer> findMaxesInCounter(int[] counter) {
52
      int max = 0;
53
      for (int i = 0; i < counter.length; i++) {
54
          max = Math.max(max, counter[i]);
55
      }
56
      List<Integer> result = new ArrayList<>();
57
      for (int i = 0; i < counter.length; i++) {
58
          if (counter[i] == max) {
59
              result.add(i);
60
          }
61
      }
62
      return result;
63
  }
64
  */
65
}