Press "Enter" to skip to content

Posts tagged as “priority queue”

่Šฑ่Šฑ้…ฑ LeetCode 2558.ย Take Gifts From the Richest Pile

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 <= 103
  • 1 <= gifts[i] <= 109
  • 1 <= k <= 103

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++

่Šฑ่Šฑ้…ฑ LeetCode 2233. Maximum Product After K Increments

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 109 + 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 <= 105
  • 0 <= nums[i] <= 106

Solution: priority queue

Always increment the smallest number. Proof?

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

C++

่Šฑ่Šฑ้…ฑ LeetCode 1882. Process Tasks Using Servers

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 jth task is inserted into the queue (starting with the 0th 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 * 105
  • 1 <= servers[i], tasks[j] <= 2 * 105

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++

่Šฑ่Šฑ้…ฑ LeetCode 1851. Minimum Interval to Include Each Query

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

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. 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 <= 105
  • 1 <= queries.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 107
  • 1 <= queries[j] <= 107

Solution: Offline Processing + Priority Queue

Similar to ่Šฑ่Šฑ้…ฑ LeetCode 1847. Closest Room

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++

่Šฑ่Šฑ้…ฑ LeetCode 1834. Single-Threaded CPU

You are given nโ€‹โ€‹โ€‹โ€‹โ€‹โ€‹ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the iโ€‹โ€‹โ€‹โ€‹โ€‹โ€‹thโ€‹โ€‹โ€‹โ€‹ task will be available to process at enqueueTimei and will take processingTimeito 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 <= 105
  • 1 <= enqueueTimei, processingTimei <= 109

Solution: Simulation w/ Sort + PQ

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

C++