Hire K workers test case fail

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.
• 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.

Link to the problem

Logic

To have two minheaps the left and the right one.

• Pop from both heaps and compare them. If left one is greater, input an added new one from the left, and push back the right element back to the heap
• If right one is greater, add a new element from the array to the right heap, push back theleft element back to the left heap as it lost the tie
• Keep adding the costs of the workers to the total_cost variable an return total_cost

Code

import heapq
from typing import List

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        left_h = []
        right_h = []
        N = len(costs)
        total_cost = 0
        left_idx = candidates - 1
        right_idx = N - candidates

        for i in range(candidates):
            heapq.heappush(left_h, costs[i])

        for i in range(right_idx, N):
            heapq.heappush(right_h, costs[i])

        i = 0
        while i < k:
            left_ele = heapq.heappop(left_h)
            right_ele = heapq.heappop(right_h)
            if left_ele <= right_ele:
                total_cost += left_ele
                heapq.heappush(right_h, right_ele)
                if left_idx + 1 < N and (right_idx == N or left_idx + 1 < right_idx):
                    heapq.heappush(left_h, costs[left_idx + 1])
                    left_idx += 1
            else:
                total_cost += right_ele
                heapq.heappush(left_h, left_ele)
                if right_idx - 1 >= 0 and (left_idx == -1 or right_idx - 1 > left_idx):
                    heapq.heappush(right_h, costs[right_idx - 1])
                    right_idx -= 1
            i += 1
        return total_cost

solution = Solution()
costs = [28,35,21,13,21,72,35,52,74,92,25,65,77,1,73,32,43,68,8,100,84,80,14,88,42,53,98,69,64,40,60,23,99,83,5,21,76,34]
k = 32
candidates = 12
print(solution.totalCost(costs, k, candidates))  # Output: 1407 # Expected: 1407

costs = [18,64,12,21,21,78,36,58,88,58,99,26,92,91,53,10,24,25,20,92,73,63,51,65,87,6,17,32,14,42,46,65,43,9,75]
k = 13
candidates = 23
print(solution.totalCost(costs, k, candidates))  # Output: 202  # Expected: 223

Issue

It fails the case given in the program.

left_idx is the index of the last inserted item on the left. right_idx is the index of the last inserted item on the right.

If you run your program, left_idx=21 and right_idx=21 so you have inserted the same item into both heaps.

Change left_idx < right_idx to left_idx + 1 < right_idx.