Chương trình tìm thời gian tối thiểu hoàn thành task với khoảng nghỉ k Python

Cho danh sách tasks (mỗi phần tử là loại task) và số k ≥ 0. Mỗi task mất 1 đơn vị thời gian, phải làm theo thứ tự, nhưng hai task cùng loại phải cách nhau ít nhất k đơn vị thời gian. Có thể chờ. Tìm tổng thời gian hoàn thành tất cả task.

Ví dụ: tasks=[0,1,1,2], k=2 → 6 (0, 1, chờ, chờ, 1, 2).

Giải thuật (Theo dõi thời gian sẵn sàng tiếp theo)

1. tick = thời gian hiện tại, slot = dict lưu thời gian sẵn sàng tiếp theo của mỗi loại task
2. Duyệt từng task t:
   • tf = slot.get(t) (thời gian sẵn sàng)
   • Nếu tf > tick: chờ đến tf (tick = tf)
   • Thực hiện task: tick += 1
   • Cập nhật slot[t] = tick + k
3. Trả về tick

Ví dụ triển khai

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

print(solve([0, 1, 1, 2], 2))

Đầu vào

[0, 1, 1, 2], 2

Đầu ra

6