Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1882.html

1882. Process Tasks Using Servers

Level

Medium

Description

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i-th server, and tasks[j] is the time needed to process the j-th task in seconds.

You are running a simulation system that will shut down after all tasks are processed. Each server can only process one task at a time. You will be able to process the j-th task starting from the j-th second beginning with the 0th task at second 0. To process task j, you assign it to the server with the smallest weight that is free, and in case of a tie, choose the server with the smallest index. If a free server gets assigned task j at second t, it will be free again at the second t + tasks[j].

If there are no free servers, you must wait until one is free and execute the free tasks as soon as possible. If multiple tasks need to be assigned, assign them in order of increasing index.

You may assign multiple tasks at the same second if there are multiple free servers.

Build an array ans of length m, where ans[j] is the index of the server the j-th task will be assigned to.

Return the array ans.

Example 1:

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]

Output: [2,2,0,2,1,2]

Explanation: Events in chronological order go as follows:

  • At second 0, task 0 is added and processed using server 2 until second 1.
  • At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
  • At second 2, task 2 is added and processed using server 0 until second 5.
  • At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
  • At second 4, task 4 is added and processed using server 1 until second 5.
  • At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2:

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]

Output: [1,4,1,4,1,3,2]

Explanation: Events in chronological order go as follows:

  • At second 0, task 0 is added and processed using server 1 until second 2.
  • At second 1, task 1 is added and processed using server 4 until second 2.
  • At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4.
  • At second 3, task 3 is added and processed using server 4 until second 7.
  • At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9.
  • At second 5, task 5 is added and processed using server 3 until second 7.
  • At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

  • servers.length == n
  • tasks.length == m
  • 1 <= n, m <= 2 * 10^5
  • 1 <= servers[i], tasks[j] <= 2 * 10^5

Solution

Use two priority queues to store the available servers and the waiting servers, respectively. The first priority queue stores each server’s weight and index, and the second priority queue stores each server’s available time, weight and index.

Initially, all servers are added to the first priority queue.

For each task, poll all servers with available time less than or equal to the current time and add them to the first priority queue. Poll one server from the first priority queue and assign the server to the current task, and add the assigned server to the second priority queue with updated available time.

  • class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = servers.length, m = tasks.length;
        int[] ans = new int[m];
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] server1, int[] server2) {
                if (server1[0] != server2[0])
                    return server1[0] - server2[0];
                else
                    return server1[1] - server2[1];
            }
        });
        for (int i = 0; i < n; i++)
            priorityQueue.offer(new int[]{servers[i], i});
        PriorityQueue<int[]> waiting = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] server1, int[] server2) {
                if (server1[0] != server2[0])
                    return server1[0] - server2[0];
                else if (server1[1] != server2[1])
                    return server1[1] - server2[1];
                else
                    return server1[2] - server2[2];
            }
        });
        int curTime = 0;
        for (int i = 0; i < m; i++) {
            curTime = Math.max(curTime, i);
            while (!waiting.isEmpty() && waiting.peek()[0] <= curTime) {
                int[] next = waiting.poll();
                priorityQueue.offer(new int[]{servers[next[2]], next[2]});
            }
            if (priorityQueue.isEmpty()) {
                int[] next = waiting.poll();
                curTime = next[0];
                priorityQueue.offer(new int[]{servers[next[2]], next[2]});
            }
            int task = tasks[i];
            int[] server = priorityQueue.poll();
            waiting.offer(new int[]{curTime + task, server[0], server[1]});
            ans[i] = server[1];
        }
        return ans;
    }
}

############

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int m = tasks.length, n = servers.length;
        PriorityQueue<int[]> idle
            = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        PriorityQueue<int[]> busy = new PriorityQueue<>((a, b) -> {
            if (a[0] == b[0]) {
                return a[1] == b[1] ? a[2] - b[2] : a[1] - b[1];
            }
            return a[0] - b[0];
        });
        for (int i = 0; i < n; ++i) {
            idle.offer(new int[] {servers[i], i});
        }
        int[] res = new int[m];
        int j = 0;
        for (int start = 0; start < m; ++start) {
            int cost = tasks[start];
            while (!busy.isEmpty() && busy.peek()[0] <= start) {
                int[] item = busy.poll();
                idle.offer(new int[] {item[1], item[2]});
            }
            if (!idle.isEmpty()) {
                int[] item = idle.poll();
                res[j++] = item[1];
                busy.offer(new int[] {start + cost, item[0], item[1]});
            } else {
                int[] item = busy.poll();
                res[j++] = item[2];
                busy.offer(new int[] {item[0] + cost, item[1], item[2]});
            }
        }
        return res;
    }
}

  • class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        idle, busy = [], []
        for i, weight in enumerate(servers):
            heappush(idle, (weight, i))
        res = []
        for start, cost in enumerate(tasks):
            while busy and busy[0][0] <= start:
                _, s, i = heappop(busy)
                heappush(idle, (s, i))
            if idle:
                s, i = heappop(idle)
                heappush(busy, (start + cost, s, i))
            else:
                t, s, i = heappop(busy)
                heappush(busy, (t + cost, s, i))
            res.append(i)
        return res

############

# 1882. Process Tasks Using Servers
# https://leetcode.com/problems/process-tasks-using-servers/

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        n = len(tasks)
        queue = []
        
        for i,x in enumerate(servers):
            queue.append((x, i))
        
        heapq.heapify(queue)
        
        running = []
        res = []
        i = t = 0
        
        while t < n:
            while running and running[0][0] <= i:
                _, capacity, index = heapq.heappop(running)
                heapq.heappush(queue, (capacity, index))
            
            while t < n and queue and i >= t:
                capacity, index = heapq.heappop(queue)
                res.append(index)

                heapq.heappush(running, (i + tasks[t], capacity, index))
                t += 1

            i = i + 1 if queue else running[0][0]
            
        return res

All Problems

All Solutions