পাইথনে সেট ও রিমูভাল কস্ট ব্যবহার করে সব আইটেম কেনার ন্যূনতম খরচ

Nটি আইটেম (০ থেকে N-1) আছে। sets লিস্টে প্রতিটি সেট [start, end, price] — অর্থাৎ price টাকা দিয়ে start থেকে end পর্যন্ত সব আইটেম পাওয়া যাবে। removals[i] = i-তম আইটেম একটা ফেলার খরচ। ঠিক একটি করে সব আইটেম পাওয়ার ন্যূনতম খরচ বের করতে হবে (সম্ভব না হলে -১)।

উদাহরণ: sets=[[0,4,4],[0,5,12],[2,6,9],[4,8,10]], removals=[2,5,4,6,8] → আউটপুট 4।

সমাধানের ধাপসমূহ (গ্রাফ + ডিকস্ট্রা / শর্টেস্ট পথ)

নোড ০ থেকে N পর্যন্ত গ্রাফ বানান।
প্রতিটি সেট [s, e, w] এর জন্য এজ s -> e+1 ওয়েট w।
প্রতিটি i এর জন্য এজ i+1 -> i ওয়েট removals[i] (আইটেম ফেলা = পিছনে যাওয়া)।
ডিকস্ট্রা অ্যালগরিদম চালিয়ে নোড ০ থেকে নোড N পর্যন্ত শর্টেস্ট পথ বের করুন।
পথ পাওয়া গেলে কস্ট রিটার্ন করুন, নাইলে -১।

পাইথন কোড উদাহরণ

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]