Posts tagged as “priority queue”

花花酱 LeetCode 2558. Take Gifts From the Richest Pile

By zxi on February 4, 2023

You are given an integer array gifts denoting the number of gifts in various piles. Every second, you do the following:

Choose the pile with the maximum number of gifts.
If there is more than one pile with the maximum number of gifts, choose any.
Leave behind the floor of the square root of the number of gifts in the pile. Take the rest of the gifts.

Return the number of gifts remaining after k seconds.

Example 1:

Input: gifts = [25,64,9,4,100], k = 4
Output: 29
Explanation: 
The gifts are taken in the following way:
- In the first second, the last pile is chosen and 10 gifts are left behind.
- Then the second pile is chosen and 8 gifts are left behind.
- After that the first pile is chosen and 5 gifts are left behind.
- Finally, the last pile is chosen again and 3 gifts are left behind.
The final remaining gifts are [5,8,9,4,3], so the total number of gifts remaining is 29.

Example 2:

Input: gifts = [1,1,1,1], k = 4
Output: 4
Explanation: 
In this case, regardless which pile you choose, you have to leave behind 1 gift in each pile. 
That is, you can't take any pile with you. 
So, the total gifts remaining are 4.

Constraints:

1 <= gifts.length <= 10³
1 <= gifts[i] <= 10⁹
1 <= k <= 10³

Solution: Priority Queue

Keep all numbers in a priority queue (max heap), each time extract the top one (largest one), then put num – sqrt(num) back to the queue.

Tip: We can early return if all the numbers become 1.

Time complexity: O(n + klogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

long long pickGifts(vector<int>& gifts, int k) {

long long ans = accumulate(begin(gifts), end(gifts), 0LL);

priority_queue<int> q(begin(gifts), end(gifts));

while (k-- && q.top() > 1) {

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

int next = sqrt(cur);

ans -= (cur - next);

q.push(next);

}

return ans;

}

};

花花酱 LeetCode 2233. Maximum Product After K Increments

By zxi on April 9, 2022

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

Solution: priority queue

Always increment the smallest number. Proof?

Time complexity: O(klogn + nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumProduct(vector<int>& nums, int k) {

constexpr int kMod = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums));

while (k--) {

const int n = q.top();

q.pop();

q.push(n + 1);

}

long long ans = 1;

while (!q.empty()) {

ans *= q.top(); q.pop();

ans %= kMod;

}

return ans;

}

};

花花酱 LeetCode 1882. Process Tasks Using Servers

By zxi on August 8, 2021

You are given two 0-indexed integer arrays servers and tasks of lengths n and m respectively. servers[i] is the weight of the i^th server, and tasks[j] is the time needed to process the j^th task in seconds.

Tasks are assigned to the servers using a task queue. Initially, all servers are free, and the queue is empty.

At second j, the j^th task is inserted into the queue (starting with the 0^th task being inserted at second 0). As long as there are free servers and the queue is not empty, the task in the front of the queue will be assigned to a free server with the smallest weight, and in case of a tie, it is assigned to a free server with the smallest index.

If there are no free servers and the queue is not empty, we wait until a server becomes free and immediately assign the next task. If multiple servers become free at the same time, then multiple tasks from the queue will be assigned in order of insertion following the weight and index priorities above.

A server that is assigned task j at second t will be free again at second t + tasks[j].

Build an array ans of length m, where ans[j] is the index of the server the j^th task will be assigned to.

Return the array ans.

Example 1:

Input: servers = [3,3,2], tasks = [1,2,3,2,1,2]
Output: [2,2,0,2,1,2]
Explanation: Events in chronological order go as follows:
- At second 0, task 0 is added and processed using server 2 until second 1.
- At second 1, server 2 becomes free. Task 1 is added and processed using server 2 until second 3.
- At second 2, task 2 is added and processed using server 0 until second 5.
- At second 3, server 2 becomes free. Task 3 is added and processed using server 2 until second 5.
- At second 4, task 4 is added and processed using server 1 until second 5.
- At second 5, all servers become free. Task 5 is added and processed using server 2 until second 7.

Example 2:

Input: servers = [5,1,4,3,2], tasks = [2,1,2,4,5,2,1]
Output: [1,4,1,4,1,3,2]
Explanation: Events in chronological order go as follows: 
- At second 0, task 0 is added and processed using server 1 until second 2.
- At second 1, task 1 is added and processed using server 4 until second 2.
- At second 2, servers 1 and 4 become free. Task 2 is added and processed using server 1 until second 4. 
- At second 3, task 3 is added and processed using server 4 until second 7.
- At second 4, server 1 becomes free. Task 4 is added and processed using server 1 until second 9. 
- At second 5, task 5 is added and processed using server 3 until second 7.
- At second 6, task 6 is added and processed using server 2 until second 7.

Constraints:

servers.length == n
tasks.length == m
1 <= n, m <= 2 * 10⁵
1 <= servers[i], tasks[j] <= 2 * 10⁵

Solution: Simulation / Priority Queue

Two priority queues, one for free servers, another for releasing events.
One FIFO queue for tasks to schedule.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> assignTasks(vector<int>& servers, vector<int>& tasks) {

const int n = servers.size();

const int m = tasks.size();

using P = pair<long, int>;

priority_queue<P, vector<P>, greater<P>> frees, release;

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

frees.emplace(servers[i], i);

vector<int> ans(m);

queue<int> q;

int l = 0;

long t = 0;

int count = 0;

while (count != m) {

// Release servers.

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

auto [rt, i] = release.top(); release.pop();

frees.emplace(servers[i], i);

}

// Enqueue tasks.

while (l < m && l <= t) q.push(l++);

// Schedule tasks.

while (q.size() && frees.size()) {

const int j = q.front(); q.pop();

auto [w, i] = frees.top(); frees.pop();

release.emplace(t + tasks[j], i);

ans[j] = i;

++count;

}

// Advance time.

if (frees.empty() && !release.empty()) {

t = release.top().first;

} else {

++t;

}

return ans;

}

};

花花酱 LeetCode 1851. Minimum Interval to Include Each Query

By zxi on May 8, 2021

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] describes the i^th interval starting at left_i and ending at right_i (inclusive). The size of an interval is defined as the number of integers it contains, or more formally right_i - left_i + 1.

You are also given an integer array queries. The answer to the j^th query is the size of the smallest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

Constraints:

1 <= intervals.length <= 10⁵
1 <= queries.length <= 10⁵
intervals[i].length == 2
1 <= left_i <= right_i <= 10⁷
1 <= queries[j] <= 10⁷

Solution: Offline Processing + Priority Queue

Sort intervals by right in descending order, sort queries in descending. Add valid intervals into the priority queue (or treeset) ordered by size in ascending order. Erase invalid ones. The first one (if any) will be the one with the smallest size that contains the current query.

Time complexity: O(nlogn + mlogm + mlogn)
Space complexity: O(m + n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {

const int n = intervals.size();

const int m = queries.size();

sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){

return a[1] > b[1];

});

vector<pair<int, int>> qs(m); // {query, i}

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

qs[i] = {queries[i], i};

sort(rbegin(qs), rend(qs));

vector<int> ans(m);

int j = 0;

priority_queue<pair<int, int>> pq; // {-size, left}

for (const auto& [query, i] : qs) {

while (j < n && intervals[j][1] >= query) {

pq.emplace(-(intervals[j][1] - intervals[j][0] + 1),

intervals[j][0]);

++j;

}

while (!pq.empty() && pq.top().second > query)

pq.pop();

ans[i] = pq.empty() ? -1 : -pq.top().first;

}

return ans;

}

};

花花酱 LeetCode 1834. Single-Threaded CPU

By zxi on April 18, 2021

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime_i, processingTime_i] means that the i^th task will be available to process at enqueueTime_i and will take processingTime_ito finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows: 
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10⁵
1 <= enqueueTime_i, processingTime_i <= 10⁹

Solution: Simulation w/ Sort + PQ

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> getOrder(vector<vector<int>>& tasks) {

const int n = tasks.size();

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

tasks[i].push_back(i);

sort(begin(tasks), end(tasks)); // sort by enqueue_time;

vector<int> ans;

priority_queue<pair<int, int>> q; // {-processing_time, -index}

int i = 0;

long t = 0;

while (ans.size() != n) {

// Advance to next enqueue time if q is empty.

if (i < n && q.empty() && tasks[i][0] > t)

t = tasks[i][0];

// Enqueue all available tasks.

while (i < n && tasks[i][0] <= t) {

q.emplace(-tasks[i][1], -tasks[i][2]);

++i;

}

// Extra the top one.

t -= q.top().first;

ans.push_back(-q.top().second);

q.pop();

}

return ans;

}

};