[C++] Set | Priority Queue | Binary Search | O(nlogk) with detailed explanation
Brute Force:\nFor each request i we traverse all servers starting from i%k and check which is the next available server and schedule the task. This will take O(
**Brute Force:**\nFor each request i we traverse all servers starting from i%k and check which is the next available server and schedule the task. This will take O(k) time to know which server should schedule the current job.\n\n**Time Complexity: O(n * k)**\n\n**Optimized Solution:**\nInstead of doing a linear search on servers for every job, it would be a good idea to use binary search instead. This will bring down the complexity for finding the next server where the job could be scheduled from O(k) to O(logk) time. \n\nTo keep the list of available servers sorted we\'ll use stl sets, lower_bound function for binay search and priority_queue to reclaim servers that are available again.\n\nThus, we can solve this problem using sets, priority_queue and lower_bound function in nlogk time.\n\n**Time Complexity: O(nlogk)\nSpace Complexity: O(k)**\n\n```\nclass Solution {\npublic:\n    \n     vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {\n\t\t // stores the number of processes scheduled on each server\n        vector<int> servers(k,0);\n\t\t\n\t\t// max number of processes scheduled\n        int max_val = 0;\n\t\t\n\t\t// for priority queue to reclaim servers that are idle now\n        auto comp = [](pair<int,int>&a, pair<int,int>&b){\n            return a.first > b.first;\n        };\n\t\t\n\t\t// priority queue stores {time when server will become free, server id}\n        priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(comp)> pq(comp);\n\t\t\n\t\t// set of available servers\n        set<int> available;\n\t\t\n        for(int i=0;i<k;i++)\n            available.insert(i);\n\t\t\t\n        for(int i=0;i<arrival.size();i++){\n            \n\t\t\t// if the time surpasses curr time reclaim server \n            while(!pq.empty() && pq.top().first<=arrival[i]){\n                available.insert(pq.top().second);\n                pq.pop();\n            }\n           \n\t\t   // if no server is available drop the request and continue\n            if(available.empty())\n                continue;\n\t\t\t\n\t\t\t// get the next available server\n            auto itr = available.lower_bound(i%k);\n\t\t\t\n\t\t\t// wrap around\n            if(itr==available.end()){\n                itr = available.begin();\n            }\n           \n\t\t    // schedule the process\n            servers[*itr]++;\n            \n            pq.push({arrival[i]+load[i],*itr});\n            int val = *itr;\n\t\t\t\n\t\t\t// mark server as known available\n            available.erase(val);\n           \n            max_val = max(max_val,servers[val]);\n\n        }\n     \n        vector<int> ans;\n\t\t\n\t\t// get all busiest servers\n        for(int i=0;i<servers.size();i++){\n            if(servers[i] == max_val)\n                ans.push_back(i);\n        }\n        \n        return ans;\n    }\n};\n```\n
[]