Chương trình tìm thời gian tối thiểu cần thiết để hoàn thành nhiệm vụ với k khoảng cách thời gian giữa các tác vụ cùng loại trong Python

Giả sử chúng ta có một danh sách các số nguyên được gọi là nhiệm vụ trong đó mỗi mục đại diện cho một loại nhiệm vụ khác nhau, chúng ta cũng có một số nguyên không âm là k. Mỗi nhiệm vụ cần một đơn vị thời gian để hoàn thành và các nhiệm vụ phải được hoàn thành theo đúng thứ tự, nhưng chúng ta phải có k đơn vị thời gian giữa hai nhiệm vụ cùng loại. Bất cứ lúc nào, chúng ta có thể thực hiện một nhiệm vụ hoặc chờ đợi. Chúng tôi phải tìm khoảng thời gian cần thiết để hoàn thành tất cả các nhiệm vụ.

Vì vậy, nếu đầu vào giống như các nhiệm vụ =[0, 1, 1, 2] k =2, thì đầu ra sẽ là 6, vì hai tác vụ đầu tiên thuộc loại khác nhau, vì vậy chúng có thể được thực hiện mà không có bất kỳ khoảng trống nào, ngay tại thời điểm 2, nhiệm vụ tiếp theo là nhiệm vụ cùng loại, chúng ta phải đợi khe thời gian 2, sau đó làm nhiệm vụ và cuối cùng là nhiệm vụ loại khác, loại 2. Vậy làm nhiệm vụ này. Vì vậy, nó giống như [0, 1, chờ đợi, chờ đợi, 1, 2]. Từ điều này, chúng tôi có thể xác định, chúng tôi cần 6 khe thời gian.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• đánh dấu:=0
• slot:=một bản đồ mới
• đối với mỗi t trong nhiệm vụ, hãy thực hiện
  • tf:=slot [t] nếu t ở trong slot
  • nếu tf không null và tf - đánh dấu> 0, thì
    • đánh dấu:=đánh dấu + tf - đánh dấu
  • đánh dấu:=đánh dấu + 1
  • slot [t]:=tick + k
• đánh dấu trả lại

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[0, 1, 1, 2]

Đầu ra

6