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

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

ดังนั้น หากอินพุตเป็น nums =[2, 2, 2, 3, 3, 2], k =1 ผลลัพธ์จะเป็น 7 เนื่องจากลำดับที่เหมาะสมที่สุดคือ [2, 3, 2, 3, 2, รอ 2].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

c :=นับค่าทั้งหมดเป็น nums
ตอบ :=0, Lastsize :=0
ในขณะที่ c ไม่ใช่ศูนย์ ให้ทำ
- Lastsize :=ขนาดของ c
- สำหรับแต่ละค่า x ในค่าทั่วไป (k + 1) ของ c ทำ
  - c[x] :=c[x] − 1
    - ถ้า c[x] เท่ากับ 0 แล้ว
      - ลบ c[x]
- ans :=ans + k + 1
ส่งคืน ans + Lastsize - (k + 1)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      from collections import Counter
      c = Counter(nums)
      ans = 0
      lastsize = 0
      while c:
         lastsize = len(c)
         for x, _ in c.most_common(k + 1):
            c[x] -= 1
            if c[x] == 0:
               del c[x]
         ans += k + 1
      return ans + lastsize - (k + 1)
ob1 = Solution()
nums = [2, 2, 2, 3, 3, 2]
k = 1
print(ob1.solve(nums, k))

อินพุต

[2, 2, 2, 3, 3, 2], 1