Skip to content

1882. Process Tasks Using Servers

  • Time: $O((n + m)\log n)$
  • Space: $O(n + m)$
 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
44
45
46
47
48
49
50
51
52
53
54
55
56
struct T {
  int weight;
  int index;
  int freeTime;
  T(int weight, int index, int freeTime)
      : weight(weight), index(index), freeTime(freeTime) {}
};

class Solution {
 public:
  vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
    const int n = servers.size();
    const int m = tasks.size();
    vector<int> ans(m);
    auto compareFree = [](const T& a, const T& b) {
      return a.weight == b.weight ? a.index > b.index : a.weight > b.weight;
    };
    auto compareUsed = [](const T& a, const T& b) {
      if (a.freeTime != b.freeTime)
        return a.freeTime > b.freeTime;
      if (a.weight != b.weight)
        return a.weight > b.weight;
      return a.index > b.index;
    };
    priority_queue<T, vector<T>, decltype(compareFree)> free(compareFree);
    priority_queue<T, vector<T>, decltype(compareUsed)> used(compareUsed);

    for (int i = 0; i < n; ++i)
      free.emplace(servers[i], i, 0);

    for (int i = 0; i < m; ++i) {  // i := the current time
      const int executionTime = tasks[i];
      // Pop all the servers that'll be free at time i.
      while (!used.empty() && used.top().freeTime <= i) {
        const T curr = used.top();
        used.pop();
        free.push(curr);
      }
      if (free.empty()) {
        T server = used.top();
        used.pop();
        ans[i] = server.index;
        server.freeTime += executionTime;
        used.push(server);
      } else {
        T server = free.top();
        free.pop();
        ans[i] = server.index;
        server.freeTime = i + executionTime;
        used.push(server);
      }
    }

    return ans;
  }
};

 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
44
45
46
47
48
49
50
51
52
53
class T {
  public int weight;
  public int index;
  public int freeTime;
  public T(int weight, int index, int freeTime) {
    this.weight = weight;
    this.index = index;
    this.freeTime = freeTime;
  }
}

class Solution {
  public int[] assignTasks(int[] servers, int[] tasks) {
    final int n = servers.length;
    final int m = tasks.length;
    int[] ans = new int[m];
    Queue<T> free = new PriorityQueue<>(
        (a, b) -> a.weight == b.weight ? a.index - b.index : a.weight - b.weight);
    Queue<T> used = new PriorityQueue<>(new Comparator<T>() {
      @Override
      public int compare(T a, T b) {
        if (a.freeTime != b.freeTime)
          return a.freeTime - b.freeTime;
        if (a.weight != b.weight)
          return a.weight - b.weight;
        return a.index - b.index;
      }
    });

    for (int i = 0; i < n; ++i)
      free.offer(new T(servers[i], i, 0));

    for (int i = 0; i < m; ++i) { // i := the current time
      final int executionTime = tasks[i];
      // Poll all servers that'll be free at time i.
      while (!used.isEmpty() && used.peek().freeTime <= i)
        free.offer(used.poll());
      if (free.isEmpty()) {
        T server = used.poll();
        ans[i] = server.index;
        server.freeTime += executionTime;
        used.offer(server);
      } else {
        T server = free.poll();
        ans[i] = server.index;
        server.freeTime = i + executionTime;
        used.offer(server);
      }
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
  def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
    ans = []
    free = []  # (weight, index, freeTime)
    used = []  # (freeTime, weight, index)

    for i, weight in enumerate(servers):
      heapq.heappush(free, (weight, i, 0))

    for i, executionTime in enumerate(tasks):  # i := the current time
      # Poll all servers that'll be free at time i.
      while used and used[0][0] <= i:
        curr = heapq.heappop(used)
        heapq.heappush(free, (curr[1], curr[2], curr[0]))
      if free:
        curr = heapq.heappop(free)
        ans.append(curr[1])
        heapq.heappush(used, (i + executionTime, curr[0], curr[1]))
      else:
        curr = heapq.heappop(used)
        ans.append(curr[2])
        heapq.heappush(used, (curr[0] + executionTime, curr[1], curr[2]))

    return ans