โปรแกรมหาเวลาน้อยที่สุดในการทำงานกับช่วงเวลาห่าง k ระหว่างงานประเภทเดียวกันใน Python

สมมติว่าเรามีรายการจำนวนเต็มชื่อ tasks แต่ละสมาชิกแทนประเภทงานต่างกัน เรายังมีจำนวนเต็มไม่ติดลบ k แต่ละงานใช้เวลา 1 หน่วย และต้องทำตามลำดับที่ถูกต้อง แต่ต้องมีช่วงเวลา k หน่วยระหว่างการทำงานประเภทเดียวกันสองครั้ง ทุกเวลา เราสามารถทำงานหรือรอได้ เราต้องหาเวลาทั้งหมดที่ใช้ทำงานทั้งหมด

เช่น ถ้าอินพุตคือ tasks = [0, 1, 1, 2], k = 2 ผลลัพธ์จะเป็น 6 เพราะงานแรกสองงานประเภทต่างกัน ทำได้ทันที ตอนเวลา 2 งานถัดไปประเภทเดียวกัน ต้องรอ 2 ช่วงเวลา แล้วทำงาน แล้วงานประเภท 2 ทำได้เลย รูปแบบคือ [0, 1, wait, wait, 1, 2] ต้องใช้ 6 ช่วงเวลา

ขั้นตอนการแก้ปัญหา

1. tick := 0
2. slot := แมปใหม่
3. สำหรับแต่ละ t ใน tasks:
   • tf := slot[t] ถ้า t ใน slot
   • ถ้า tf ไม่เป็น None และ tf - tick > 0 ให้ tick := tick + tf - tick
   • tick := tick + 1
   • slot[t] := tick + k
4. คืนค่า tick

ตัวอย่างการใช้งาน

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