You are given a 0-indexed integer array costs where costs[i] is the cost of hiring the ith worker.
You are also given two integers k and candidates. We want to hire exactly k workers according to the following rules:
k sessions and hire exactly one worker in each session.candidates workers or the last candidates workers. Break the tie by the smallest index.
costs = [3,2,7,7,1,2] and candidates = 2, then in the first hiring session, we will choose the 4th worker because they have the lowest cost [3,2,7,7,1,2].1st worker because they have the same lowest cost as 4th worker but they have the smallest index [3,2,7,7,2]. Please note that the indexing may be changed in the process.Return the total cost to hire exactly k workers.
Example 1:
Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4 Output: 11 Explanation: We hire 3 workers in total. The total cost is initially 0. - In the first hiring round we choose the worker from [17,12,10,2,7,2,11,20,8]. The lowest cost is 2, and we break the tie by the smallest index, which is 3. The total cost = 0 + 2 = 2. - In the second hiring round we choose the worker from [17,12,10,7,2,11,20,8]. The lowest cost is 2 (index 4). The total cost = 2 + 2 = 4. - In the third hiring round we choose the worker from [17,12,10,7,11,20,8]. The lowest cost is 7 (index 3). The total cost = 4 + 7 = 11. Notice that the worker with index 3 was common in the first and last four workers. The total hiring cost is 11.
Example 2:
Input: costs = [1,2,4,1], k = 3, candidates = 3 Output: 4 Explanation: We hire 3 workers in total. The total cost is initially 0. - In the first hiring round we choose the worker from [1,2,4,1]. The lowest cost is 1, and we break the tie by the smallest index, which is 0. The total cost = 0 + 1 = 1. Notice that workers with index 1 and 2 are common in the first and last 3 workers. - In the second hiring round we choose the worker from [2,4,1]. The lowest cost is 1 (index 2). The total cost = 1 + 1 = 2. - In the third hiring round there are less than three candidates. We choose the worker from the remaining workers [2,4]. The lowest cost is 2 (index 0). The total cost = 2 + 2 = 4. The total hiring cost is 4.
Constraints:
1 <= costs.length <= 105 1 <= costs[i] <= 1051 <= k, candidates <= costs.lengthIn 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.
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.
JavaScript
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.
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.
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.
Java
Time Complexity: O(n log candidates) to sort.
Space Complexity: O(candidates) for storing and sorting the two halves.
| Approach | Complexity |
|---|---|
| Min-Heap Approach | Time Complexity: O(k * log(candidates)), where k is the number of workers to hire and candidates the number from both ends considered. |
| Two Pointers with Sorted Segments | Time Complexity: O(n log candidates) to sort. |
Minimum Cost to Hire K Workers - Leetcode 857 - Python • NeetCodeIO • 16,851 views views
Watch 9 more video solutions →Practice Total Cost to Hire K Workers with our built-in code editor and test cases.
Practice on FleetCode