Chương trình lên lịch tác vụ để tốn ít thời gian nhất trong Python

Giả sử chúng ta có một danh sách giá trị gọi là tasks, trong đó mỗi giá trị khác nhau đại diện cho một loại tác vụ khác nhau, và chúng ta cũng có một số nguyên không âm k. Mỗi tác vụ mất một phút để hoàn thành, nhưng chúng ta phải chờ k phút giữa việc thực hiện hai tác vụ cùng loại. Tại bất kỳ thời điểm nào, chúng ta có thể đang làm một tác vụ hoặc đang chờ. Chúng ta phải tìm lượng thời gian nhỏ nhất để hoàn thành tất cả các tác vụ.

Ví dụ, nếu đầu vào là nums = [2, 2, 2, 3, 3, 2], k = 1, thì đầu ra sẽ là 7, vì thứ tự tối ưu là [2, 3, 2, 3, 2, WAITING, 2].

Để giải quyết, chúng ta thực hiện các bước sau:

• c := đếm tất cả giá trị trong nums
• ans := 0, lastsize := 0
• trong khi c không rỗng:
  • lastsize := kích thước của c
  • với mỗi giá trị x trong (k + 1) giá trị phổ biến nhất của c:
    • c[x] := c[x] - 1
    • nếu c[x] bằng 0, xóa c[x]
  • ans := ans + k + 1
• trả về ans + lastsize - (k + 1)

Ví dụ

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

Input

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

Output

7