Sponsored
Sponsored
In this approach, we use a min-heap to keep track of the candidate workers with the lowest costs. By maintaining a collection of candidate workers from both ends of the list, the algorithm efficiently selects and removes the minimum worker for each session. This helps follow the hierarchical hiring order by prioritizing the smallest cost and index.
Time Complexity: O(k * log(candidates)), where k is the number of workers to hire and candidates the number from both ends considered.
Space Complexity: O(candidates) for maintaining the two heaps.
1import heapq
2
3def total_cost(costs, k, candidates):
4 left_candidates = [(cost, i) for i, cost in enumerate(costs[:candidates])]
5 right_candidates = [(cost, i) for i, cost in enumerate(costs[-candidates:], start=len(costs)-candidates)]
6
7 heapq.heapify(left_candidates)
8 heapq.heapify(right_candidates)
9
10 total_cost = 0
11 hired_workers = set()
12
13 for _ in range(k):
14 while left_candidates and left_candidates[0][1] in hired_workers:
15 heapq.heappop(left_candidates)
16 while right_candidates and right_candidates[0][1] in hired_workers:
17 heapq.heappop(right_candidates)
18
19 if (left_candidates and (not right_candidates or left_candidates[0][0] < right_candidates[0][0] or
20 (left_candidates[0][0] == right_candidates[0][0] and left_candidates[0][1] <= right_candidates[0][1]))):
21 cost, index = heapq.heappop(left_candidates)
22 else:
23 cost, index = heapq.heappop(right_candidates)
24
25 total_cost += cost
26 hired_workers.add(index)
27
28 return total_cost
29
30# Example usage:
31print(total_cost([17,12,10,2,7,2,11,20,8], 3, 4))
32print(total_cost([1,2,4,1], 3, 3))The Python solution uses two heaps to maintain the workers with the lowest costs from both the beginning and the end of the list. By popping the minimum cost worker in each session, it ensures the optimal choice based on cost and then index if there's a tie. The workers are marked as hired so they are not reconsidered in subsequent rounds.
This approach involves sorting segments of the array and using two pointers to dynamically track the smallest available candidate from the start and end. By maintaining sorted sections, it allows for efficient extraction by moving pointers closer as sessions proceed.
Time Complexity: O(n log candidates) to sort.
Space Complexity: O(candidates) for storing and sorting the two halves.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int totalCost(vector<int>& costs, int k, int candidates) {
vector<pair<int, int>> left(costs.begin(), costs.begin() + candidates);
vector<pair<int, int>> right(costs.end() - candidates, costs.end());
sort(left.begin(), left.end());
sort(right.begin(), right.end());
int totalCost = 0;
int l_ptr = 0, r_ptr = 0;
for (int i = 0; i < k; ++i) {
if (l_ptr < candidates && (r_ptr >= candidates || left[l_ptr].first <= right[r_ptr].first)) {
totalCost += left[l_ptr].first;
l_ptr++;
} else {
totalCost += right[r_ptr].first;
r_ptr++;
}
}
return totalCost;
}
// Example usage:
// vector<int> costs = {17,12,10,2,7,2,11,20,8};
// cout << totalCost(costs, 3, 4);The C++ solution sorts two sections of the costs array corresponding to available candidates. Two pointers select the minimum between the two candidate lists in each hiring session, maintaining the principle of hiring the least costly worker first.