โปรแกรมรับผลกำไรสูงสุดโดยการจัดตารางงานใน Python

สมมติว่าเรามีรายการของช่วงเวลาที่แต่ละช่วงมีค่าสามค่า [start, end, profit] เราสามารถดำเนินการได้ครั้งละหนึ่งงานเท่านั้น เราต้องหากำไรให้ได้มากที่สุด

ดังนั้น ถ้าอินพุตเหมือนช่วง =[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]] ผลลัพธ์จะเป็น 350 เนื่องจากเราสามารถหาสองช่วงเวลา [1, 2, 100] และ [2, 100, 250]

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

• d :=แผนที่ว่างที่มีรายการเป็นค่า
• n :=0
• สำหรับแต่ละ (เริ่มต้น สิ้นสุด กำไร) ในช่วงเวลา ทำ
  • ถ้าสิ้นสุด> n แล้ว
    • n :=จบ
• ใส่คู่ (เริ่ม, สิ้นสุด) ลงใน d[end]
• A :=รายการขนาด n + 1 และเติมด้วย 0
• สำหรับจุดสิ้นสุดในช่วง 0 ถึงขนาด A ให้ทำ
  • ถ้าสิ้นสุดอยู่ใน d แล้ว
    • สำหรับแต่ละคู่ (เริ่มต้น, กำไร) ใน d[end], do
      • A[end] :=สูงสุดของ A[end], (A[start] + กำไร) และ A[end - 1]
  • มิฉะนั้น
    • A[end] :=A[end - 1]
• คืนค่าสุดท้ายของ A

ตัวอย่าง (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 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))

อินพุต

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

ผลลัพธ์

350