สมมติว่าเรามีงานจำนวนมากที่มีความต้องการด้านเวลาต่างกัน มีบุคคล k คนที่จะมอบหมายงานและเรามีเวลาเท่าใดที่ผู้ได้รับมอบหมายใช้ในการทำงานหน่วยเดียว เราต้องหาเวลาขั้นต่ำในการทำงานทั้งหมดให้เสร็จสิ้นโดยมีข้อจำกัดดังต่อไปนี้
-
มอบหมายได้เฉพาะงานที่ต่อเนื่องกันเท่านั้น
-
ผู้ได้รับมอบหมายสองคนไม่สามารถแบ่งปันหรือทำงานเดียวได้
ดังนั้น หากอินพุตเป็น k =4, t =5, job ={12, 6, 9, 15, 5, 9} ผลลัพธ์จะเป็น 75 ตามที่เราได้รับในครั้งนี้โดยกำหนด [12],[6 , 9],[15] และ [5, 9]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน is_valid() ต้องใช้เวลาครับ K งาน
-
n :=ขนาดของงาน
-
จำนวน :=1, curr_time :=0, i :=0
-
ในขณะที่ฉัน
-
ถ้าcurr_time + job[i]> เวลา แล้ว
-
curr_time :=0
-
นับ :=นับ + 1
-
-
มิฉะนั้น
-
curr_time :=curr_time + job[i]
-
ผม :=ผม + 1
-
-
-
คืนค่าจริงเมื่อนับ <=K
-
จากวิธีหลัก ให้ทำดังนี้
-
n :=ขนาดของงาน
-
สิ้นสุด :=0, เริ่มต้น :=0
-
สำหรับผมอยู่ในช่วง 0 ถึง n ทำ
-
end :=end + job[i]
-
-
res :=จบ
-
job_max :=จำนวนงานสูงสุด
-
ขณะที่เริ่ม <=สิ้นสุด ทำ
-
mid :=((begin + end) / 2) นำจำนวนเต็ม
-
ถ้า mid>=job_max และ is_valid(mid, K, job) เป็นจริง แล้ว
-
res :=ความละเอียดขั้นต่ำ, กลาง
-
end :=mid - 1
-
-
มิฉะนั้น
-
เริ่มต้น :=กลาง + 1
-
-
-
ผลตอบแทน * T
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def is_valid(time, K, job): n = len(job) count = 1 curr_time = 0 i = 0 while i < n: if curr_time + job[i] > time: curr_time = 0 count += 1 else: curr_time += job[i] i += 1 return count <= K def get_minimum_time(K, T, job): n = len(job) end = 0 begin = 0 for i in range(n): end += job[i] res = end job_max = max(job) while begin <= end: mid = int((begin + end) / 2) if mid >= job_max and is_valid(mid, K, job): res = min(res, mid) end = mid - 1 else: begin = mid + 1 return res * T job = [12, 6, 9, 15, 5, 9] k = 4 T = 5 print(get_minimum_time(k, T, job))
อินพุต
4, 5, [12, 6, 9, 15, 5, 9]
ผลลัพธ์
75
