Total Cost to Hire K Workers

The key idea

Problem

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. You want to hire exactly k workers according to the following rules:

- You will run k sessions and hire exactly one worker in each session.
- In each hiring session, choose the worker with the lowest cost from either the first candidates workers or the last candidates workers. Break the tie by the smallest index.
- If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them, breaking the tie by the smallest index.
- A worker can only be chosen once.

Return the total cost to hire exactly k workers.

Constraints

• 1 <= costs.length <= 10^5
• 1 <= costs[i] <= 10^5
• 1 <= k, candidates <= 10^5

Examples

Complexity

Time: O((k + candidates) log candidates) Space: O(candidates)

More Heap / Priority Queue problems

• Find K Pairs with Smallest SumsMEDIUM
• Find Median from Data StreamHARD
• IPOHARD
• K Closest Points to OriginMEDIUM
• Kth Largest Element in a StreamEASY
• Kth Largest Element in an ArrayMEDIUM
• Last Stone WeightEASY
• Maximum Subsequence ScoreMEDIUM
• Meeting Rooms IIMEDIUM
• Meeting Rooms IIIHARD
• Merge k Sorted ListsHARD
• Minimum Interval to Include Each QueryHARD