ข้อ 52 · LC2462 Total Cost to Hire K Workers (ต้นทุนจ้าง k คน) 🟡

โจทย์ (LC2462): กำหนด array จำนวนเต็ม costs โดย costs[i] คือค่าจ้างของคนงานคนที่ i พร้อมจำนวนเต็ม k และ candidates ให้ทำการ hire (จ้างงาน) ทั้งหมด k รอบ รอบละหนึ่งคน แต่ละรอบให้เลือกคนที่ค่าจ้างถูกที่สุดจาก candidates คนแรกสุดของแถวที่เหลือ หรือ candidates คนท้ายสุดของแถวที่เหลือ (ถ้าเท่ากันให้เลือก index น้อยกว่า) ถ้าคนที่เหลือมีน้อยกว่า candidates คน ให้เลือกจากคนที่เหลือทั้งหมด คนแต่ละคนถูกจ้างได้ครั้งเดียว ให้ return ผลรวมต้นทุนการจ้างทั้งหมด

แนวทาง — ต้องใช้อะไร & คิดยังไง

โครงสร้างที่ใช้: min-heap สองอัน อันหนึ่งคุมฝั่งหัวแถว อีกอันคุมฝั่งท้ายแถว การหาตัวถูกสุด (minimum) ของแต่ละฝั่งซ้ำ ๆ คือหน้าที่ของ min-heap พอดี

คิดแบบง่าย/ช้าก่อน: ถ้าแต่ละรอบ scan (ไล่สแกน) หาค่าถูกสุดใน window (หน้าต่าง) หัว-ท้ายเองจะเป็น O(k * candidates) และการ remove/เลื่อนคนใน array ก็แพง เราจึงใช้ heap สองอันให้ pop ตัวถูกสุดของแต่ละฝั่งได้ที่ O(log candidates)

1. สร้าง head จาก candidates คนแรก และ tail จาก candidates คนท้าย โดยกันช่วงทับกันด้วยจุดเริ่ม max(candidates, n - candidates) แล้ว heapify ทั้งสอง
2. initialize pointer (ตัวชี้) left และ right ชี้คนตรงกลางที่ยังไม่ถูกดึงเข้า heap
3. iterate k รอบ: compare head[0] กับ tail[0] เลือกฝั่งที่ถูกกว่า (ถ้าเท่ากันเลือกหัว เพราะ index น้อยกว่า) pop ออกแล้วบวกเข้า total
4. หลัง hire ฝั่งไหน ถ้า left <= right ยังไม่ชนกัน ให้ push คนใหม่จากตรงกลาง (costs[left] หรือ costs[right]) เข้า heap ฝั่งนั้น แล้วขยับ pointer

ไล่ทีละสเต็ป

จำลอง costs = [17,12,10,2,7,2,11,20,8], k = 3, candidates = 4 (n = 9) เริ่ม head = [17,12,10,2], tail = [7,2,11,20,8] ที่ index 4..8 (จุดเริ่ม max(4,5)=5 → จริง ๆ tail = [2,11,20,8]), left = 4, right = 4:

total = 11

import heapq

def total_cost(costs, k, candidates):
    n = len(costs)
    left = candidates          # pointer ถัดไปฝั่งหัว
    right = n - 1 - candidates  # pointer ถัดไปฝั่งท้าย

    head = costs[:candidates]              # candidates คนแรก
    tail = costs[max(candidates, n - candidates):]  # candidates คนท้าย (ไม่ทับกับหัว)
    heapq.heapify(head)
    heapq.heapify(tail)

    total = 0
    for _ in range(k):
        # เลือกฝั่งที่ถูกกว่า ถ้าเท่ากันเลือกฝั่งหัว (index น้อยกว่า)
        if not tail or (head and head[0] <= tail[0]):
            total += heapq.heappop(head)
            # เติมคนใหม่จากตรงกลางเข้าฝั่งหัว ถ้ายังไม่ชนกัน
            if left <= right:
                heapq.heappush(head, costs[left])
                left += 1
        else:
            total += heapq.heappop(tail)
            if left <= right:
                heapq.heappush(tail, costs[right])
                right -= 1
    return total

print(total_cost([17, 12, 10, 2, 7, 2, 11, 20, 8], 3, 4))  # 11
print(total_cost([1, 2, 4, 1], 3, 3))  # 4

11
4