Leetcode 2462: Total Cost to Hire K Workers
You are given an array of integers where each element represents the cost of hiring a worker. You need to hire exactly k workers by running k sessions. In each session, choose the worker with the lowest cost from either the first ‘candidates’ workers or the last ‘candidates’ workers. If there is a tie, choose the worker with the smallest index.
Problem
Approach
Steps
Complexity
Input: You are given three values: the costs array, k (the number of workers to hire), and candidates (the number of workers to consider from both the beginning and end of the remaining workers).
Example: costs = [5, 8, 3, 1, 6, 2], k = 2, candidates = 3
Constraints:
• 1 <= costs.length <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= k, candidates <= costs.length
Output: Return the total cost of hiring exactly k workers following the selection rule.
Example: For costs = [5, 8, 3, 1, 6, 2], k = 2, candidates = 3, the output is 4.
Constraints:
• The result should be an integer.
Goal: To hire exactly k workers by choosing from the first 'candidates' workers or the last 'candidates' workers based on the minimum cost and smallest index for ties.
Steps:
• Initialize a priority queue to track the lowest cost workers.
• Iterate through the first 'candidates' and last 'candidates' workers, pushing them into the queue.
• For each of the k hiring sessions, pop the worker with the lowest cost and smallest index from the queue.
• After each hiring session, update the queue with the next possible workers from both the beginning and end.
Goal: Ensure that the number of workers selected is exactly k and the workers are chosen according to the rules.
Steps:
• k workers need to be hired, with each worker chosen from the first 'candidates' or last 'candidates' workers based on the minimum cost.
Assumptions:
• The workers are chosen according to the lowest cost with the smallest index for ties.
• Once a worker is chosen, they are no longer available for subsequent selections.
• Input: For costs = [5, 8, 3, 1, 6, 2], k = 2, candidates = 3
• Explanation: In the first hiring session, we choose the worker with the cost of 1 (index 3), and in the second session, we choose the worker with the cost of 3 (index 2), totaling 4.
Approach: Use a priority queue (min-heap) to select the lowest cost worker at each session from the first 'candidates' workers or the last 'candidates' workers.
Observations:
• We need to keep track of the workers in the first and last 'candidates' positions.
• A priority queue will help efficiently select the worker with the lowest cost.
• Ensure that the heap is updated after each selection to reflect the remaining candidates.
Steps:
• Initialize two pointers to track the left and right candidates.
• Push the first 'candidates' and last 'candidates' workers into the priority queue.
• For each hiring session, pop the lowest cost worker, add their cost to the total, and update the queue with the next possible workers.
Empty Inputs:
• If the costs array is empty, return 0.
Large Inputs:
• If the array is large, ensure the solution is optimized for time complexity.
Special Values:
• If all workers have the same cost, select the worker with the smallest index.
Constraints:
• The solution must handle up to 100,000 workers efficiently.
long long totalCost(vector<int>& costs, int k, int cand) {
long long cost = 0;
int n = costs.size();
int l = cand - 1, r = n - cand; // inclusive
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
if(l >= r) {
for(int i = 0; i < n; i++)
pq.push({costs[i], i});
while(k--) {
cost += pq.top()[0];
pq.pop();
}
return cost;
}
int i = 0;
while(i <= l) {
pq.push({costs[i], i});
i++;
}
i = n - 1;
while(i >= r) {
pq.push({costs[i], i});
i--;
}
while(k--) {
auto it = pq.top();
pq.pop();
cost += it[0];
if(it[1] <= l && l < r - 1) {
l++;
pq.push({costs[l], l});
} else if(it[1] >= r && l < r - 1) {
r--;
pq.push({costs[r], r});
}
}
return cost;
}
1 : Function Declaration
long long totalCost(vector<int>& costs, int k, int cand) {
The function signature defining inputs: a cost array, the number of workers 'k,' and a candidate range 'cand.'
2 : Variable Initialization
long long cost = 0;
Initialize the total cost to zero.
3 : Variable Initialization
int n = costs.size();
Determine the size of the input cost array.
4 : Variable Initialization
int l = cand - 1, r = n - cand; // inclusive
Set up the left and right candidate range boundaries.
5 : Priority Queue Initialization
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
Declare a min-heap priority queue to manage costs and indices.
6 : Condition Check
if(l >= r) {
Check if the left and right boundaries overlap, indicating all elements can be pushed directly.
7 : Loop
for(int i = 0; i < n; i++)
Iterate through the entire cost array to push elements into the priority queue.
8 : Priority Queue Operation
pq.push({costs[i], i});
Push the cost and index pair into the priority queue.
9 : Loop
while(k--) {
Iterate to extract the minimum 'k' costs from the priority queue.
10 : Priority Queue Operation
cost += pq.top()[0];
Add the minimum cost from the top of the queue.
11 : Priority Queue Operation
pq.pop();
Remove the top element from the priority queue.
12 : Return
return cost;
Return the total minimum cost when all workers are selected.
13 : Loop
while(i <= l) {
Push elements from the left boundary range into the priority queue.
14 : Priority Queue Operation
pq.push({costs[i], i});
Push left-side candidates into the priority queue.
15 : Loop
while(i >= r) {
Push elements from the right boundary range into the priority queue.
16 : Priority Queue Operation
pq.push({costs[i], i});
Push right-side candidates into the priority queue.
17 : Priority Queue Operation
auto it = pq.top();
Extract the current minimum cost element.
18 : Condition Check
if(it[1] <= l && l < r - 1) {
Check if the selected candidate is from the left and adjust the boundary.
19 : Priority Queue Operation
pq.push({costs[l], l});
Push the next candidate from the left boundary.
20 : Condition Check
} else if(it[1] >= r && l < r - 1) {
Check if the selected candidate is from the right and adjust the boundary.
21 : Priority Queue Operation
pq.push({costs[r], r});
Push the next candidate from the right boundary.
Best Case: O(k log k)
Average Case: O(k log k)
Worst Case: O(k log k)
Description: Each operation (insertion and removal) in the priority queue takes O(log k), and we perform k operations.
Best Case: O(k)
Worst Case: O(k)
Description: The space complexity is O(k) due to the storage required for the priority queue to manage the workers.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus