โปรแกรมหาต้นทุนต่ำสุดซื้อของครบทุกชนิดใน Python

คำอธิบายโจทย์

มี N ชนิดของ 0..N-1 สามารถซื้อ set[i] = [start, end, price] ได้ของ start..end รวม หรือทิ้งของ i ราคา removals[i] หาต้นทุนต่ำสุดได้ของทุกชนิด 1 ชิ้นพอดี

ตัวอย่าง

sets = [[0,4,4],[0,5,12],[2,6,9],[4,8,10]], removals = [2,5,4,6,8] → 4

วิธีแก้ปัญหา

Shortest Path (Dijkstra) บนกราฟ:

1. Node 0..N แทน "ได้ของ 0..i-1 แล้ว"
2. Edge: ซื้อ set [s,e,w] → จาก s ไป e+1 ค่า w
3. Edge: ทิ้งของ i → จาก i+1 ไป i ค่า removals[i]
4. หา shortest path 0 → N

โค้ด Python

import heapq
from collections import defaultdict

class Solution:
    def solve(self, sets, removals):
        N = len(removals)
        graph = [[] for _ in range(N + 1)]
        for s, e, w in sets:
            graph[s].append([e + 1, w])
        for i, r in enumerate(removals):
            graph[i + 1].append([i, r])
        
        pq = [[0, 0]]
        dist = defaultdict(lambda: float("inf"))
        dist[0] = 0
        
        while pq:
            d, e = heapq.heappop(pq)
            if dist[e] < d:
                continue
            if e == N:
                return d
            for nei, w in graph[e]:
                d2 = d + w
                if d2 < dist[nei]:
                    dist[nei] = d2
                    heapq.heappush(pq, [d2, nei])
        return -1

ob = Solution()
print(ob.solve([
    [0, 4, 4],
    [0, 5, 12],
    [2, 6, 9],
    [4, 8, 10]
], [2, 5, 4, 6, 8]))

อินพุต

[[0,4,4],[0,5,12],[2,6,9],[4,8,10]], [2,5,4,6,8]

เอาต์พุต

4