สมมติว่าเรามีรายการจำนวนเต็มที่เรียกว่างาน ซึ่งแต่ละรายการแทนประเภทงานที่แตกต่างกัน เราก็มีเลขจำนวนเต็มไม่เป็นลบเช่น k งานแต่ละงานใช้เวลาหนึ่งหน่วยในการดำเนินการให้เสร็จ และงานต้องเสร็จสิ้นในลำดับที่ถูกต้อง แต่เราต้องมีหน่วยเวลา k หน่วยระหว่างการทำงานประเภทเดียวกันสองงาน เมื่อใดก็ตามที่เราสามารถทำงานหรือรอ เราต้องหาระยะเวลาที่ใช้ในการทำงานทั้งหมดให้เสร็จ
ดังนั้น หากอินพุตเป็นเหมือนงาน =[0, 1, 1, 2] k =2 ผลลัพธ์จะเป็น 6 เนื่องจากงานสองรายการแรกเป็นประเภทที่แตกต่างกัน จึงสามารถดำเนินการได้โดยไม่มีช่องว่าง ณ เวลานี้ 2 งานต่อไปเป็นงานประเภทเดียวกัน ต้องรอ 2 เวลาจึงทำงานและสุดท้ายมีงานประเภทอื่น งานประเภทที่ 2 ให้ทำภารกิจนี้ มันก็เหมือนกับ [0, 1, wait, wait, 1, 2] จากนี้เราสามารถระบุได้ว่าเราต้องการช่วงเวลา 6 ช่วงเวลา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ติ๊ก :=0
- สล็อต :=แผนที่ใหม่
- สำหรับแต่ละ t ในงาน ทำ
- tf :=slot[t] ถ้า t อยู่ใน slot
- ถ้า tf ไม่เป็นค่าว่าง และ tf - ติ๊ก> 0 แล้ว
- ติ๊ก :=ติ๊ก + tf - ติ๊ก
- ขีด :=ขีด + 1
- สล็อต[t] :=ขีด + k
- ติ๊กกลับ
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
def solve(tasks, k):
tick = 0
slot = {}
for t in tasks:
tf = slot.get(t)
if tf is not None and tf - tick > 0:
tick += tf - tick
tick += 1
slot[t] = tick + k
return tick
tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k)) อินพุต
[0, 1, 1, 2]
ผลลัพธ์
6
