Total Cost to Hire K Workers

題目描述

給定一個成本陣列 costs，一個整數 k（要雇用人數）和整數 candidates。每輪從前 candidates 個或後 candidates 個中選成本最低的工人雇用，回傳雇用 k 人的總成本。

輸入：costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4
輸出：11
解釋：第 1 輪挑 costs[3]=2，第 2 輪挑 costs[5]=2，第 3 輪挑 costs[2]=7，總成本=11

解題思路

初始化雙 Heap

左 Heap 放 costs[0..candidates-1]，右 Heap 放 costs[n-candidates..n-1]，用 left/right 指標追蹤下一個待加入的索引

避免重疊

維護 left 和 right 指標，只在 left ≤ right 時加入新候選人，防止同一人被兩個 Heap 同時包含

每輪取最小

peek 兩個 Heap 頂端，取值較小的那個（相同時取左邊的，因為題目要求取索引較小者）

補充候選人

從被取走的那一側補入下一個候選人。例如取左 Heap → costs[left] 加入左 Heap，left++

重複 K 次

重複 K 輪，每輪取一個最便宜的工人，累加成本到 totalCost

程式碼

C#

csharp

public class Solution {
    public long TotalCost(int[] costs, int k, int candidates) {
        int n = costs.Length;
        var leftHeap = new PriorityQueue<int, int>();
        var rightHeap = new PriorityQueue<int, int>();
        int left = 0, right = n - 1;
        
        // 初始化：各放 candidates 個
        for (int i = 0; i < candidates && left <= right; i++) {
            leftHeap.Enqueue(costs[left], costs[left]);
            left++;
        }
        for (int i = 0; i < candidates && left <= right; i++) {
            rightHeap.Enqueue(costs[right], costs[right]);
            right--;
        }
        
        long totalCost = 0;
        for (int i = 0; i < k; i++) {
            int leftMin = leftHeap.Count > 0 ? leftHeap.Peek() : int.MaxValue;
            int rightMin = rightHeap.Count > 0 ? rightHeap.Peek() : int.MaxValue;
            
            if (leftMin <= rightMin) {
                totalCost += leftHeap.Dequeue();
                if (left <= right) {
                    leftHeap.Enqueue(costs[left], costs[left]);
                    left++;
                }
            } else {
                totalCost += rightHeap.Dequeue();
                if (left <= right) {
                    rightHeap.Enqueue(costs[right], costs[right]);
                    right--;
                }
            }
        }
        return totalCost;
    }
}

TypeScript

typescript

function totalCost(costs: number[], k: number, candidates: number): number {
    const n = costs.length;
    // 使用排序陣列模擬 min heap
    const leftHeap: number[] = [];
    const rightHeap: number[] = [];
    let left = 0, right = n - 1;
    
    // 初始化
    for (let i = 0; i < candidates && left <= right; i++) {
        leftHeap.push(costs[left++]);
    }
    for (let i = 0; i < candidates && left <= right; i++) {
        rightHeap.push(costs[right--]);
    }
    leftHeap.sort((a, b) => a - b);
    rightHeap.sort((a, b) => a - b);
    
    let totalCost = 0;
    for (let i = 0; i < k; i++) {
        const lMin = leftHeap.length > 0 ? leftHeap[0] : Infinity;
        const rMin = rightHeap.length > 0 ? rightHeap[0] : Infinity;
        
        if (lMin <= rMin) {
            totalCost += leftHeap.shift()!;
            if (left <= right) {
                // 插入並保持排序
                const val = costs[left++];
                const idx = leftHeap.findIndex(x => x > val);
                leftHeap.splice(idx === -1 ? leftHeap.length : idx, 0, val);
            }
        } else {
            totalCost += rightHeap.shift()!;
            if (left <= right) {
                const val = costs[right--];
                const idx = rightHeap.findIndex(x => x > val);
                rightHeap.splice(idx === -1 ? rightHeap.length : idx, 0, val);
            }
        }
    }
    return totalCost;
}

Python

python

import heapq
 
def totalCost(costs: list[int], k: int, candidates: int) -> int:
    n = len(costs)
    left_heap, right_heap = [], []
    left, right = 0, n - 1
    
    # 初始化雙 heap
    for _ in range(candidates):
        if left <= right:
            heapq.heappush(left_heap, costs[left])
            left += 1
    for _ in range(candidates):
        if left <= right:
            heapq.heappush(right_heap, costs[right])
            right -= 1
    
    total = 0
    for _ in range(k):
        l_min = left_heap[0] if left_heap else float('inf')
        r_min = right_heap[0] if right_heap else float('inf')
        
        if l_min <= r_min:
            total += heapq.heappop(left_heap)
            if left <= right:
                heapq.heappush(left_heap, costs[left])
                left += 1
        else:
            total += heapq.heappop(right_heap)
            if left <= right:
                heapq.heappush(right_heap, costs[right])
                right -= 1
    
    return total

複雜度分析

| | Time | Space | |--|------|-------| | 本解法 | O((k + candidates) log candidates) | O(candidates) |

Time：初始化放入 2 × candidates 個元素各一次 heap push O(log candidates)，之後 K 輪每輪做一次 pop + 一次 push，合計 O((k + candidates) log candidates)
Space：兩個 Heap 各最多 candidates 個元素，合計 O(candidates)

圖解

Left Heap (前 candidates 個)

peek→

Right Heap (後 candidates 個)

peek→

比較兩 Heap 最小值

取 min→

取較小者，累加成本

補充→

從對應方向補充候選人

圖表展示了雙 Heap 的核心運作：左右各維護一個 Min Heap，每輪 peek 兩端取最小值。取走後從對應方向補入新候選人，left/right 指標向中間靠攏直到交會後停止補充。

進階觀點

💡面試追問

為什麼要用兩個 Heap 而不是一個？ 左右兩側的「補充來源」不同——左 Heap 取走後從 left 指標向右補，右 Heap 從 right 指標向左補。合成一個 Heap 無法區分該從哪一側補充新候選人。
左右指標重疊時怎麼辦？ 當 left > right 時，中間已無剩餘工人，停止補充即可。兩個 Heap 消耗已有的元素繼續比較，直到選滿 K 人。
如果 2 × candidates ≥ n 會怎樣？ 所有工人都在初始候選中，問題退化為「從 n 個人中選最便宜的 K 個」，直接排序取前 K 小即可。

邊界情況

k 等於 n：必須雇用所有人，答案就是 costs 的總和
candidates 等於 1：每輪只能看到最左邊和最右邊各一個人，模擬兩端逐步向中間的選擇過程
所有 costs 相同：每輪取哪一邊都一樣，答案固定為 k × cost 值

理解測驗

🤔 為什麼需要兩個 Min Heap 而不是一個？

🤔 當 left > right 時代表什麼？