[c++] Segment tree + priority queue + explanation
Observation\n1) A naive attempt to get the next server which is not busy will lead to TLE, so how can we optimize it ? My answer is Segment Tree\n2) In fact, th
# Observation\n1) A naive attempt to get the next server which is not busy will lead to TLE, so how can we optimize it ? My answer is Segment Tree\n2) In fact, the arrival time of request is sorted, so we can find all server that is not or no more busy using priority queue. We just need to compare the earliest ending (arrival time + processing time)\n\n# Complexity\n- Time complexity: $$O(k + n(1 + logk + logn))$$\n\n- Space complexity: $$O(k + n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c++\nclass Solution {\npublic:\n    vector<int> tree;\n    void construct_tree(int k) {\n        for (int i = 0; i < k; i++) tree[i+k] = i;\n        for (int i = k-1; i > 0; --i) tree[i] = min(tree[i*2], tree[i*2 | 1]);\n    }\n\n    int query(int k, int l, int r) {\n        l += k; r += k;\n        int res = INT_MAX;\n        while (l < r) {\n            if (l & 1) res = min(res, tree[l++]);\n            if (r & 1) res = min(res, tree[--r]);\n            l /= 2; r /= 2;\n        }\n        return res;\n    }\n\n    void update(int k, int i, int val) {\n        for (tree[i += k] = val; i > 1; i /= 2)\n            tree[i/2] = min(tree[i], tree[1^i]);\n    }\n\n    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {\n        vector<bool> busy(k);\n        int n = arrival.size();\n        tree.resize(k*2, INT_MAX);\n        unordered_map<int, int> count;\n        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;\n\n        construct_tree(k);\n        for (int i = 0; i < n; ++i) {\n            while (!pq.empty() && pq.top().first <= arrival[i]) {\n                int server_id = pq.top().second; pq.pop();\n                update(k, server_id, server_id); // mark as available\n                busy[server_id] = false;\n            }\n\n            int server_id = i % k;\n            if (!busy[server_id]) {\n                count[server_id]++;\n                busy[server_id] = true;\n                pq.push( make_pair(arrival[i] + load[i], server_id) );\n                update(k, server_id, INT_MAX); // mark as unavailable\n                continue;\n            }\n\n            int id = INT_MAX;\n            // find next available\n            if (server_id + 1 < k) {\n                id = query(k, server_id + 1, k);\n                if (id == INT_MAX) id = query(k, 0, server_id);\n            }\n            else id = query(k, 0, k);\n        \n            //there is no available server\n            if (id == INT_MAX)\n                continue;\n\n            count[id]++;\n            busy[id] = true;\n            update(k, id, INT_MAX); \n            pq.push( make_pair(arrival[i] + load[i], id) );\n        }\n\n        int max_freq = 0;\n        for (auto &[_, v] : count)\n            max_freq = max(max_freq, v);\n\n        vector<int> res;\n        for (auto &[server_id, v] : count) \n            if (max_freq == v)\n                res.push_back(server_id);\n\n        return res;\n    }\n};\n```
['C++']