Description

Submission

class Solution {
    typedef array<int, 2> AI2;
    typedef array<int, 3> AI3;
public:
    vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {
        
        priority_queue<AI2, vector<AI2>, greater<>> servers_pq;  // {weight, index}
        priority_queue<AI3, vector<AI3>, greater<>> process_pq;  // {end_time, weight, index}
        queue<int> jobs;

        for(int i = 0; i < servers.size(); ++i) {
            servers_pq.push({servers[i], i});
        }

        vector<int> rets;
        
        for(int j = 0; j < tasks.size(); ++j) { // t is guarantted to be larger than j
            // collect from the process_pq, make sure servers_pq having available servers
            jobs.push(j);

            while(!process_pq.empty()) {
                auto [end_time, weight, index] = process_pq.top();
                if(end_time <= j) {
                    process_pq.pop();
                    servers_pq.push({weight, index});
                } else {
                    break;
                }
            }

            while(!jobs.empty() && !servers_pq.empty()) {
                auto [weight, index] = servers_pq.top();
                int task = jobs.front();
                jobs.pop();
                servers_pq.pop();
                process_pq.push({j + tasks[task], weight, index});
                rets.push_back(index); 
            }
        }

        while(!jobs.empty()) {
            int job = jobs.front();
            jobs.pop();
            auto [end_time, weight, index] = process_pq.top();
            process_pq.pop();
            rets.push_back(index);
            process_pq.push({end_time + tasks[job], weight, index});
        }

        return rets;
    }
};