process-tasks-using-servers.cpp

// Time:  O(n + mlogn)
// Space: O(n)

class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        vector<pair<int, int>> idle;
        for (int i = 0; i < size(servers); ++i) {
            idle.emplace_back(servers[i], i);
        }
        make_heap(begin(idle), end(idle), greater<>());
        vector<tuple<int, int, int>> working;

        vector<int> result;
        for (int i = 0, t = 0; i < size(tasks); ++i) {
            t = !empty(idle) ? max(t, i) : get<0>(working.front());
            while (!empty(working) && get<0>(working.front()) <= t) {
                const auto [_, w, idx] = working.front(); pop_heap(begin(working), end(working), greater<>()); working.pop_back();
                idle.emplace_back(w, idx); push_heap(begin(idle), end(idle), greater<>());
            }
            const auto [w, idx] = idle.front(); pop_heap(begin(idle), end(idle), greater<>()); idle.pop_back();
            working.emplace_back(t + tasks[i], w, idx); push_heap(begin(working), end(working), greater<>());
            result.emplace_back(idx);
        }
        return result;
    }
};