How hard is LeetCode 2462. Total Cost to Hire K Workers?

LeetCode 2462. Total Cost to Hire K Workers is rated Medium on LeetCode.

What is the time complexity of LeetCode 2462. Total Cost to Hire K Workers?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 2462. Total Cost to Hire K Workers?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2462. Total Cost to Hire K Workers cover?

LeetCode 2462. Total Cost to Hire K Workers is tagged Array, Two Pointers, Simulation and Heap (Priority Queue) on LeetCode.

Total Cost to Hire K Workers — LeetCode 2462 Python Solution

MediumArrayTwo PointersSimulationHeap (Priority Queue)

Problem: #2462
Pattern: Heap / Priority Queue
Reading time: 5 min
Source: leetcode.com

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

Example

Input: costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
Output: 11
Explanation: We hire 3 workers in total. The total cost is initially 0.

Python solution

Python

class Solution:
    def totalCost(self, costs: List[int], k: int, candidates: int) -> int:
        n = len(costs)
        if candidates * 2 >= n:
            return sum(sorted(costs)[:k])
        pq = []
        for i, c in enumerate(costs[:candidates]):
            heappush(pq, (c, i))
        for i in range(n - candidates, n):
            heappush(pq, (costs[i], i))
        heapify(pq)
        l, r = candidates, n - candidates - 1
        ans = 0
        for _ in range(k):
            c, i = heappop(pq)
            ans += c
            if l > r:
                continue
            if i < l:
                heappush(pq, (costs[l], l))
                l += 1
            else:
                heappush(pq, (costs[r], r))
                r -= 1
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2462. Total Cost to Hire K Workers is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

On a study list

This problem is on LeetCode 75.

Frequently asked questions

How hard is LeetCode 2462. Total Cost to Hire K Workers?: LeetCode 2462. Total Cost to Hire K Workers is rated Medium on LeetCode.
What is the time complexity of LeetCode 2462. Total Cost to Hire K Workers?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 2462. Total Cost to Hire K Workers?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2462. Total Cost to Hire K Workers cover?: LeetCode 2462. Total Cost to Hire K Workers is tagged Array, Two Pointers, Simulation and Heap (Priority Queue) on LeetCode.