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

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

เช่น intervals = [[1, 2, 100], [3, 5, 40], [6, 19, 150], [2, 100, 250]] ผลลัพธ์ = 350 เลือกงาน [1, 2, 100] และ [2, 100, 250]

ขั้นตอนการแก้ปัญหา (DP + Group by End Time)

• d := defaultdict(list) จัดกลุ่มงานตาม end time
• n := max(end)
• A := array ขนาด n+1 เติม 0 โดย A[t] = กำไรสูงสุดจนถึงเวลา t
• วน end = 0..n:
  • ถ้า end in d: วนทุก (start, profit) ใน d[end]: A[end] = max(A[end], A[start] + profit, A[end-1])
  • มิฉะนั้น: A[end] = A[end-1]
• คืน A[-1]

ตัวอย่างโค้ด

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