LC-2462 Medium LeetCode

2462. Total Cost to Hire K Workers

Array Two Pointers Heap (Priority Queue) Simulation

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 43% Topics: Array, Two Pointers, Heap (Priority Queue), Simulation

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  O(c + klogc)
# Space: O(c)

import heapq


# heap, two pointers
class Solution(object):
    def totalCost(self, costs, k, candidates):
        """
        :type costs: List[int]
        :type k: int
        :type candidates: int
        :rtype: int
        """
        left, right = candidates, max(len(costs)-candidates, candidates)-1
        min_heap1, min_heap2 = costs[:left], costs[right+1:]
        heapq.heapify(min_heap1), heapq.heapify(min_heap2)
        result = 0
        for _ in xrange(k):
            if not min_heap2 or (min_heap1 and min_heap1[0] <= min_heap2[0]):
                result += heapq.heappop(min_heap1)
                if left <= right:
                    heapq.heappush(min_heap1, costs[left])
                    left += 1
            else:
                result += heapq.heappop(min_heap2)
                if left <= right:
                    heapq.heappush(min_heap2, costs[right])
                    right -= 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT