โจทย์: มีงานหลายงาน แต่ละงานใช้เวลาต่างกัน มี k คน ทำงานคนละหน่วยใช้เวลา t หาเวลารวมน้อยที่สุด โดย: 1) คนละคนทำงานติดกัน (contiguous) 2) งานหนึ่งไม่สามารถแบ่งให้หลายคน
ตัวอย่าง: k=4, t=5, jobs=[12,6,9,15,5,9] → จัดกลุ่ม [12], [6,9], [15], [5,9] → max sum = 15 → เวลา = 15×5 = 75
อัลกอริทึม: Binary Search on Answer
- ค้นหาคำตอบในช่วง [max(jobs), sum(jobs)]
- ฟังก์ชัน
is_valid(limit): ตรวจสอบว่าจัดกลุ่มได้ ≤ k กลุ่ม โดยแต่ละกลุ่ม sum ≤ limit - ถ้า valid → ลด limit (end = mid-1) มิฉะนั้นเพิ่ม limit (begin = mid+1)
- คำตอบสุดท้าย × t
ตัวอย่างโค้ด
def is_valid(time_limit, K, jobs):
count = 1
curr = 0
for job in jobs:
if curr + job > time_limit:
curr = 0
count += 1
curr += job
return count <= K
def get_minimum_time(K, T, jobs):
end = sum(jobs)
begin = 0
res = end
job_max = max(jobs)
while begin <= end:
mid = (begin + end) // 2
if mid >= job_max and is_valid(mid, K, jobs):
res = min(res, mid)
end = mid - 1
else:
begin = mid + 1
return res * T
jobs = [12, 6, 9, 15, 5, 9]
print(get_minimum_time(4, 5, jobs)) # 75
ผลลัพธ์
75
สรุป: Classic "Allocate Minimum Number of Pages / Painters Partition" problem ใช้ Binary Search on Answer + Greedy validation
