treeset Archives - Page 2 of 2 - Huahua's Tech Road

Solution: Priority Queue

If we double an odd number it becomes an even number, then we can only divide it by two which gives us back the original number. So we can pre-double all the odd numbers and only do division in the following process.

We push all numbers including pre-doubled odd ones onto a priority queue, and track the difference between the largest and smallest number.

Each time, we pop the largest number out and divide it by two then put it back to the priority queue, until the largest number becomes odd. We can not discard it and divide any other smaller numbers by two will only increase the max difference, so we can stop here.

ex1: [3, 5, 8] => [6, 8, 10] (pre-double) => [5, 6, 8] => [4, 5, 6] => [3, 4, 5] max diff is 5 – 3 = 2
ex2: [4,1,5,20,3] => [2, 4, 6, 10, 20] (pre-double) => [2, 4, 6, 10] => [2, 4, 5, 6] => [2,3,4,5] max diff = 5-2 = 3

Time complexity: O(n*logm*logn)
Space complexity: O(n)

C++/Set

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

set<int> s;

for (int x : nums)

s.insert(x & 1 ? x * 2 : x);

int ans = *rbegin(s) - *begin(s);

while (*rbegin(s) % 2 == 0) {

s.insert(*rbegin(s) / 2);

s.erase(*rbegin(s));

ans = min(ans, *rbegin(s) - *begin(s));

}

return ans;

}

};

C++/PQ

class Solution {

public:

int minimumDeviation(vector<int>& nums) {

priority_queue<int> q;

int lo = INT_MAX;

for (int x : nums) {

x = x & 1 ? x * 2 : x;

q.push(x);

lo = min(lo, x);

}

int ans = q.top() - lo;

while (q.top() % 2 == 0) {

int x = q.top(); q.pop();

q.push(x / 2);

lo = min(lo, x / 2);

ans = min(ans, q.top() - lo);

}

return ans;

}

};

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

The i^th (0-indexed) request arrives.
If all servers are busy, the request is dropped (not handled at all).
If the (i % k)^th server is available, assign the request to that server.
Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the i^th server is busy, try to assign the request to the (i+1)^th server, then the (i+2)^th server, and so on.

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the i^th request, and another array load, where load[i] represents the load of the i^th request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Example 1:

Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
Output: [1] 
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.

Example 2:

Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.

Example 3:

Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.

Example 4:

Input: k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]
Output: [1]

Example 5:

Input: k = 1, arrival = [1], load = [1]
Output: [0]

Constraints:

1 <= k <= 10⁵
1 <= arrival.length, load.length <= 10⁵
arrival.length == load.length
1 <= arrival[i], load[i] <= 10⁹
arrival is strictly increasing.

Solution: Heap + TreeSet

Use a min heap to store the release time -> server.
Use a treeset to track the current available servers.
For reach request, check whether servers can be released at that time.

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {

priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> q; // {release_time, server}

set<int> servers;

vector<int> requests(k);

for (int i = 0; i < k; ++i)

servers.insert(i);

for (int i = 0; i < arrival.size(); ++i) {

const int t = arrival[i];

const int l = load[i];

// Release servers. O(logk) per pop()

while (!q.empty() && q.top().first <= t) {

servers.insert(q.top().second);

q.pop();

}

// Drop the request.

if (servers.empty()) continue;

// Find first avaiable one O(logk)

auto it = servers.lower_bound(i % k);

if (it == servers.end()) it = begin(servers);

const int idx = *it;

++requests[idx];

servers.erase(it);

q.emplace(t + l, idx);

}

const int max_req = *max_element(begin(requests), end(requests));

vector<int> ans;

for (int i = 0; i < k; ++i)

if (requests[i] == max_req) ans.push_back(i);

return ans;

}

};

Posts tagged as “treeset”

花花酱 LeetCode 1675. Minimize Deviation in Array

Solution: Priority Queue

C++/Set

C++/PQ

花花酱 LeetCode 1606. Find Servers That Handled Most Number of Requests

Solution: Heap + TreeSet

C++