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.
1import java.util.Arrays;
2
3
Java's implementation sorts both sides of potential workers and uses a pointer comparison method to decide the sequence of hiring decisions. As it hires, it adds the selected worker to the total cost after each session.