Untitled

mail@pastecode.io avatar
unknown
python
7 months ago
1.8 kB
8
Indexable
Never
class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        def find_smallest_element(cost_temp, start, end):
            if len(cost_temp) == 1:
                return 0
            while start < end:
                if cost_temp[start] > cost_temp[end]:
                    start += 1
                else:
                    end -= 1
            return start

        total = 0
        for i in range(k):
            costs_len = len(costs)
            # check if there are less workers than candidates
            if costs_len < candidates:
                idx_smallest = find_smallest_element(costs, 0, costs_len - 1)
                total += costs[idx_smallest]
                costs.pop(idx_smallest)
                continue
            
            # find the index of the smallest element in the left half
            costs_left = costs[0: candidates]
            idx_sml_left = find_smallest_element(costs_left, 0, candidates-1)

            # find the index of the smallest element in the right half
            costs_right = costs[costs_len - candidates : ]
            idx_sml_right = find_smallest_element(costs_right, 0, candidates-1)
            idx_smal_right_abs = costs_len - candidates + idx_sml_right

            # check the ultimate smallest and break the tie
            if idx_sml_left == idx_smal_right_abs:
                total += costs[idx_sml_left]
                costs.pop(idx_sml_left)

            elif costs[idx_sml_left] <= costs[idx_smal_right_abs]:
                total += costs[idx_sml_left]
                costs.pop(idx_sml_left)
            
            else:
                total += costs[idx_smal_right_abs]
                costs.pop(idx_smal_right_abs)
        
        return total
Leave a Comment