Chương trình tìm lợi nhuận lớn nhất bằng cách lên lịch công việc trong Python

Cho danh sách các công việc intervals, mỗi công việc là [start, end, profit]. Chỉ làm một công việc tại một thời điểm. Tìm tổng lợi nhuận tối đa.

Ví dụ: [[1,2,100],[3,5,40],[6,19,150],[2,100,250]] → chọn công việc 1 và 4 → tổng 350.

Giải thuật (DP theo thời gian kết thúc)

• Nhóm công việc theo thời gian kết thúc end trong từ điển d.
• Tìm n = max(end).
• Mảng A kích thước n+1, A[t] = lợi nhuận max đến thời điểm t.
• Duyệt end từ 0 đến n:
  • Nếu có công việc kết thúc tại end: A[end] = max(A[end], A[start] + profit, A[end-1]).
  • Ngược lại: A[end] = A[end-1].
• Trả về A[-1].

Mã nguồn Python

from collections import defaultdict

class Solution:
    def solve(self, intervals):
        d = defaultdict(list)
        n = 0
        for start, end, profit in intervals:
            if end > n:
                n = end
            d[end].append([start, profit])
        A = [0] * (n + 1)
        for end in range(len(A)):
            if end in d:
                for start, profit in d[end]:
                    A[end] = max(A[end], A[start] + profit, A[end - 1])
            else:
                A[end] = A[end - 1]
        return A[-1]

ob = Solution()
intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]]
print(ob.solve(intervals))  # Output: 350

Đầu vào

[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]

Đầu ra

350