1882. Process Tasks Using Servers

/**
 * Problem: LeetCode 1882 - Process Tasks Using Servers
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    public int[] assignTasks(int[] servers, int[] tasks) {
        int n = servers.length, m = tasks.length;

        // free: {weight, index}
        PriorityQueue<int[]> free = new PriorityQueue<>((a, b) ->
            a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        // busy: {freeTime, weight, index}
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) -> {
            if (a[0] != b[0]) return Long.compare(a[0], b[0]);
            if (a[1] != b[1]) return Long.compare(a[1], b[1]);
            return Long.compare(a[2], b[2]);
        });

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

        int[] ans = new int[m];
        long t = 0;

        for (int j = 0; j < m; j++) {
            t = Math.max(t, j);

            // Release servers that are free by time t
            while (!busy.isEmpty() && busy.peek()[0] <= t) {
                long[] s = busy.poll();
                free.offer(new int[]{(int) s[1], (int) s[2]});
            }

            // No free server: jump to the earliest free time
            if (free.isEmpty()) {
                t = busy.peek()[0];
                while (!busy.isEmpty() && busy.peek()[0] <= t) {
                    long[] s = busy.poll();
                    free.offer(new int[]{(int) s[1], (int) s[2]});
                }
            }

            int[] best = free.poll();
            ans[j] = best[1];
            busy.offer(new long[]{t + tasks[j], best[0], best[1]});
        }

        return ans;
    }
}

"""
Problem: LeetCode 1882 - Process Tasks Using Servers
Difficulty: Medium
Language: Python (Python 3)
Author: CodeByTushu
"""
from typing import List
import heapq

class Solution:
    def assignTasks(self, servers: List[int], tasks: List[int]) -> List[int]:
        n = len(servers)
        m = len(tasks)
        
        # free heap: (weight, index)
        free = [(servers[i], i) for i in range(n)]
        heapq.heapify(free)
        
        # busy heap: (free_time, weight, index)
        busy = []
        
        ans = [0] * m
        t = 0
        
        for j in range(m):
            t = max(t, j)
            
            # Release servers that are free by time t
            while busy and busy[0][0] <= t:
                free_time, weight, idx = heapq.heappop(busy)
                heapq.heappush(free, (weight, idx))
                
            # No free server: jump to the earliest free time
            if not free:
                t = busy[0][0]
                while busy and busy[0][0] <= t:
                    free_time, weight, idx = heapq.heappop(busy)
                    heapq.heappush(free, (weight, idx))
                    
            weight, idx = heapq.heappop(free)
            ans[j] = idx
            heapq.heappush(busy, (t + tasks[j], weight, idx))
            
        return ans

/**
 * Problem: LeetCode 1882 - Process Tasks Using Servers
 * Difficulty: Medium
 * Language: C++ (C++20)
 * Author: CodeByTushu
 */
#include <vector>
#include <queue>
#include <tuple>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        int n = servers.size(), m = tasks.size();

        // free: (weight, index)
        using FreeServer = pair<int, int>;
        priority_queue<FreeServer, vector<FreeServer>, greater<FreeServer>> free;

        // busy: (freeTime, weight, index)
        using BusyServer = tuple<long long, int, int>;
        priority_queue<BusyServer, vector<BusyServer>, greater<BusyServer>> busy;

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

        vector<int> ans(m);
        long long t = 0;

        for (int j = 0; j < m; j++) {
            t = max(t, (long long)j);

            // Release servers that are free by time t
            while (!busy.empty() && get<0>(busy.top()) <= t) {
                auto [freeTime, weight, idx] = busy.top();
                busy.pop();
                free.emplace(weight, idx);
            }

            // No free server: jump to the earliest free time
            if (free.empty()) {
                t = get<0>(busy.top());
                while (!busy.empty() && get<0>(busy.top()) <= t) {
                    auto [freeTime, weight, idx] = busy.top();
                    busy.pop();
                    free.emplace(weight, idx);
                }
            }

            auto [bestWeight, bestIdx] = free.top();
            free.pop();
            ans[j] = bestIdx;
            busy.emplace(t + tasks[j], bestWeight, bestIdx);
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 1882 - Process Tasks Using Servers
 * Difficulty: Medium
 * Language: JavaScript (Node.js ES2022)
 * Author: CodeByTushu
 */

class MinHeap {
    constructor(compare) {
        this.heap = [];
        this.compare = compare;
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    peek() {
        return this.heap[0];
    }

    push(val) {
        this.heap.push(val);
        this._siftUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this._siftDown(0);
        }
        return top;
    }

    _siftUp(idx) {
        while (idx > 0) {
            const parent = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[parent]) < 0) {
                [this.heap[idx], this.heap[parent]] = [this.heap[parent], this.heap[idx]];
                idx = parent;
            } else {
                break;
            }
        }
    }

    _siftDown(idx) {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = (idx << 1) + 1;
            const right = left + 1;

            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

/**
 * @param {number[]} servers
 * @param {number[]} tasks
 * @return {number[]}
 */
var assignTasks = function(servers, tasks) {
    const n = servers.length;
    const m = tasks.length;

    // free: [weight, index]
    const free = new MinHeap((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        return a[1] - b[1];
    });

    // busy: [freeTime, weight, index]
    const busy = new MinHeap((a, b) => {
        if (a[0] !== b[0]) return a[0] - b[0];
        if (a[1] !== b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });

    for (let i = 0; i < n; i++) {
        free.push([servers[i], i]);
    }

    const ans = new Int32Array(m);
    let t = 0;

    for (let j = 0; j < m; j++) {
        t = Math.max(t, j);

        // Release servers that are free by time t
        while (!busy.isEmpty() && busy.peek()[0] <= t) {
            const s = busy.pop();
            free.push([s[1], s[2]]);
        }

        // No free server: jump to the earliest free time
        if (free.isEmpty()) {
            t = busy.peek()[0];
            while (!busy.isEmpty() && busy.peek()[0] <= t) {
                const s = busy.pop();
                free.push([s[1], s[2]]);
            }
        }

        const best = free.pop();
        ans[j] = best[1];
        busy.push([t + tasks[j], best[0], best[1]]);
    }

    return Array.from(ans);
};