Skip to content

1606. Find Servers That Handled Most Number of Requests 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
 public:
  vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
    vector<int> ans;
    vector<int> times(k);
    set<int> idleServers;
    // (endTime, server)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;

    for (int i = 0; i < k; ++i)
      idleServers.insert(i);

    for (int i = 0; i < arrival.size(); ++i) {
      // Pop all the servers that are available now.
      while (!minHeap.empty() && minHeap.top().first <= arrival[i]) {
        idleServers.insert(minHeap.top().second);
        minHeap.pop();
      }
      // Get the next available server.
      const int server = getNextAvailableServer(idleServers, i, k);
      if (server == -1)
        continue;
      ++times[server];
      minHeap.emplace(arrival[i] + load[i], server);
      idleServers.erase(server);
    }

    const int busiest = ranges::max(times);
    for (int i = 0; i < k; ++i)
      if (times[i] == busiest)
        ans.push_back(i);
    return ans;
  }

 private:
  int getNextAvailableServer(const set<int>& idleServers, int ithRequest,
                             int k) {
    if (idleServers.empty())
      return -1;
    const auto it = idleServers.lower_bound(ithRequest % k);
    return it == idleServers.cend() ? *idleServers.begin() : *it;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
    List<Integer> ans = new ArrayList<>();
    int[] times = new int[k];
    TreeSet<Integer> idleServers = new TreeSet<>();
    // (endTime, server)
    Queue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>(Comparator.comparing(Pair::getKey));

    for (int i = 0; i < k; ++i)
      idleServers.add(i);

    for (int i = 0; i < arrival.length; ++i) {
      // Pop all the servers that are available now.
      while (!minHeap.isEmpty() && minHeap.peek().getKey() <= arrival[i]) {
        idleServers.add(minHeap.peek().getValue());
        minHeap.poll();
      }
      // Get the next available server.
      final int server = getNextAvailableServer(idleServers, i, k);
      if (server == -1)
        continue;
      ++times[server];
      minHeap.offer(new Pair<>(arrival[i] + load[i], server));
      idleServers.remove(server);
    }

    final int busiest = Arrays.stream(times).max().getAsInt();
    for (int i = 0; i < k; ++i)
      if (times[i] == busiest)
        ans.add(i);
    return ans;
  }

  private int getNextAvailableServer(TreeSet<Integer> idleServers, int ithRequest, int k) {
    if (idleServers.isEmpty())
      return -1;
    Integer server = idleServers.ceiling(ithRequest % k);
    return server == null ? idleServers.first() : server;
  }
}