2462. Total Cost to Hire K Workers

[fockspaces]

everytime we pick min cost from first k elements or last k elements. we can simply using for loop to lookup the suitable value each time, but will TLE eventually

the best way is to use space to record the next ready to pop out value from each side, then keep filling candiadate for each side

1. create left_half and right_half as heapq for tracking the values
2. make sure two heapq have full elements if any for add before comparing
3. decide which to pop out, untill k decrease to zero

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        ans = 0
        left_half, right_half = [], []
        n = len(costs)
        l, r = 0, n - 1
        while k:
            while l <= r and len(left_half) < candidates:
                heappush(left_half, costs[l])
                l += 1
            while l <= r and len(right_half) < candidates:
                heappush(right_half, costs[r])
                r -= 1
            min_from_left = float('inf') if not left_half else left_half[0]
            min_from_right = float('inf') if not right_half else right_half[0]
            if min_from_left <= min_from_right:
                ans += heappop(left_half)
            else:
                ans += heappop(right_half)
            k -= 1
        return ans

[fockspaces]

the ternary condiftion will check if first, so we can write like this one without index Erorr:

min_from_left = left_half[0] if left_half else float('inf')
min_from_right = right_half[0] if right_half else float('inf')