< Back





2462. Total Cost to Hire K Workers

We're given a list of workers and asked to hire them in k rounds. We're allowed to pick candidates
workers from the list, starting from the front and the back of the list during each round. The
cheaper candidate will be added to the total cost, and removed from future consideration. Ties are
broken by index in the list.

To solve this, we maintain two pointers for our front and back processing of candidates. As we
eliminate candidates from consideration, depending on which half of the list we choose from, we'll
move the pointer forward.

All of the candidates selected by the two pointers, from the head and tail, are added to a heap. As
candidates leave the heap, new candidates are pushed from the head or tail of the list, depending on
which half of the list they were selected from.

Once the head and tail cross each other, we stop pushing candidates to the heap to avoid duplicates.

The solution is as follows:


  from heapq import heapify, heappop, heappush

  class Solution:
      def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
          n, h, ans = len(costs), [], 0
          next_head, next_tail = candidates, n - 1 - candidates

          for i in range(candidates):
              h.append((costs[i], 0))

          for i in range(max(candidates, n - candidates), n):
              h.append((costs[i], 1))

          heapify(h)

          for _ in range(k):
              cost, section = heappop(h)
              ans += cost

              if next_head <= next_tail:
                  if section == 0:
                      heappush(h, (costs[next_head], 0))
                      next_head += 1
                  else:
                      heappush(h, (costs[next_tail], 1))
                      next_tail -= 1

          return ans


_ Time Complexity:

  O((k + m) * log(m)) - We conduct k rounds of hiring, and for each round, we push and pop from the
  heap, which has a size of m.

_ Space Complexity:

  O(m) - Where m is the number of candidates we're considering.