LeetCode 1882. Process Tasks Using Servers

Posted on Edited on In 
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
typedef pair<long long, int> PLI;
typedef pair<int, int> PII;
class Solution {
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        const int n = tasks.size();
        priority_queue<PLI, vector<PLI>, greater<PLI>> busy; // <t, idx>
        priority_queue<PII, vector<PII>, greater<PII>> idle; // <w, idx>
        for (int i = 0; i < servers.size(); ++i)
            idle.emplace(servers[i], i);
        long long t = -1;
        auto release = [&]() {
            while (!busy.empty() && busy.top().first <= t) {
                auto [_, idx] = busy.top(); busy.pop();
                idle.emplace(servers[idx], idx);
            }
        };
        vector<int> ans(n);
        for (int i = 0; i < n; ++i) {
            t = max(t, static_cast<long long> (i));
            release();
            if (idle.empty()) {
                t = busy.top().first;
                release();
            }
            auto [_, idx] = idle.top(); idle.pop();
            ans[i] = idx;
            busy.emplace(t + tasks[i], idx);
        }
        return ans;
    }
};