2462. Total Cost to Hire K Workers

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. We 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.
  • For example, if 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].
  • In the second hiring session, we will choose 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.
• If there are fewer than candidates workers remaining, choose the worker with the lowest cost among them. Break 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 <= costs.length

Reevaluate¶

• A find min problem: Heap, Min Binary Tree
• We only need to find the lowest cost in first cost[0:candidates] and last cost[len-1 - candidates : len], so we could used some dynamic left right pointer and a: Heap

Solving with heap¶

1. Create a left heap and right heap
2. Push cost[0:candidates] to left heap and cost[len-1 - candidates : len] to right heap
3. Pop ether head of left and right heap then push next correspond from cost table back to the heap
4. Run it k time

Actual code¶

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left = []
        right = []

        for value in costs[:candidates]:
            heapq.heappush(left, value)
        for value in costs[max(candidates, len(costs) - candidates):]:
            heapq.heappush(right, value)

        pointerLeft = candidates - 1
        pointerRight = len(costs) - candidates
        total = 0
        for i in range(k):
            if left == [] and right == []:
                break

            if left == []:
                total += heapq.heappop(right)
                continue
            elif right == []:
                total += heapq.heappop(left)
                continue

            if left[0] <= right[0]:
                total += heapq.heappop(left)
                if pointerLeft + 1 < pointerRight:
                    pointerLeft += 1
                    heapq.heappush(left, costs[pointerLeft])
            else:
                total += heapq.heappop(right)
                if pointerLeft < pointerRight - 1:
                    pointerRight -= 1
                    heapq.heappush(right, costs[pointerRight])

        return total