Chương trình để đạt được lợi nhuận tối đa bằng cách lên lịch công việc bằng Python

Giả sử chúng ta có một danh sách các khoảng trong đó mỗi khoảng chứa ba giá trị [bắt đầu, kết thúc, lợi nhuận]. Chúng ta chỉ có thể thực hiện một nhiệm vụ tại một thời điểm, chúng ta phải tìm ra mức lợi nhuận cao nhất mà chúng ta có thể nhận được.

Vì vậy, nếu đầu vào giống như khoảng =[[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]], thì đầu ra sẽ là 350, vì chúng ta có thể lấy hai khoảng này [1, 2, 100] và [2, 100, 250]

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

• d:=một bản đồ trống có chứa các danh sách dưới dạng các giá trị
• n:=0
• đối với mỗi (bắt đầu, kết thúc, lợi nhuận) trong các khoảng thời gian, hãy thực hiện
  • nếu end> ​​n, thì
    • n:=end
• chèn cặp (bắt đầu, kết thúc) vào d [end]
• A:=danh sách có kích thước n + 1 và điền bằng 0
• để kết thúc trong phạm vi từ 0 đến kích thước là A, thực hiện
  • nếu kết thúc bằng d, thì
    • đối với mỗi cặp (bắt đầu, lợi nhuận) trong d [end], thực hiện
      • A [end]:=tối đa A [end], (A [start] + lợi nhuận) và A [end - 1]
  • nếu không,
    • A [end]:=A [end - 1]
• trả về giá trị cuối cùng của A

Ví dụ (Python)

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

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 for i in range(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))

Đầu vào

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

Đầu ra

350