2462. Total Cost to Hire K Workers

Leetcode link

题目简介

/**
 * @param {number[]} costs
 * @param {number} k
 * @param {number} candidates
 * @return {number}
 */

题目给我们一个数字数组 costs 代表招募每个员工需要的成本；k 代表我们要进行 k 轮招募，每次只能招募一名员工；candidates 表示我们每一轮招募员工的候选人，分别是 costs 的前 candidates 个员工与后 candidates 个员工

最后要求我们求出我们招募 k 名员工最低需要多少成本

解题思路

由于每次招募候选人都是前 candidates 个与后 candidates 个，所以我们可以使用两个小顶堆 leftHeap 与 rightHeap 来分别保存两边的候选人

在每一轮开始前，我们都要保证两个 heap 中都有 candidates 个员工（由于可能出现剩余员工总数小于 candidates*2 的情况，所以我们需要额外用 left 与 right 下标来标记当前进入候选的员工边界）

接下来我们只需要判断两个 heap 哪一个的顶点元素最小，然后将其 pop 出来并合并成本返回即可

最后为了防止某个堆因为人数不足而为空的情况，我们可以提前给两个堆都 push 进去一个最大的整数来避免

Javascript

/**
 * @param {number[]} costs
 * @param {number} k
 * @param {number} candidates
 * @return {number}
 */
var totalCost = function (costs, k, candidates) {
    const len = costs.length
    let left = 0
    let right = len - 1
    const leftMinHeap = new PriorityQueue((a, b) => a - b)
    const rightMinHeap = new PriorityQueue((a, b) => a - b)
    // prevent one of them is empty
    leftMinHeap.push(Number.MAX_SAFE_INTEGER)
    rightMinHeap.push(Number.MAX_SAFE_INTEGER)
    let res = 0

    for (let i = 0; i < k; i++) {
        while(leftMinHeap.size() <= candidates && left <= right) {
            leftMinHeap.push(costs[left++])
        }
        while(rightMinHeap.size() <= candidates && right >= left) {
            rightMinHeap.push(costs[right--])
        }
        if(leftMinHeap.front() <= rightMinHeap.front()) {
            res += leftMinHeap.pop()
        } else {
            res += rightMinHeap.pop()
        }
    }

    return res
};

复杂度分析

n 代表 costs 的数量，c 代表 candidates 的数量

时间

分为两个部分：

• push 堆：堆有两个，每次遍历 k 时最多会 push n 次堆，每次 push 的成本是 O(logc)，所以是 O(nlogc)
• pop 堆：总共会 pop k 次，每次成本是 O(logc)，所以是 O(klogc)

加总起来是 O((n+k)logc)

空间

主要来源为两个 heap，所以是 O(c)