পাইথনে জব শিডিউলিং দিয়ে সর্বোচ্চ প্রফিট বের করার প্রোগ্রাম

একটি ইন্টারভাল লিস্ট দেওয়া আছে, প্রতিটি ইন্টারভাল: [start, end, profit]। একবারে একটি টাস্ক করা যায়। ওভারল্যাপ না করে সর্বোচ্চ প্রফিট বের করতে হবে।

উদাহরণস্বরূপ, intervals = [[1,2,100],[3,5,40],[6,19,150],[2,100,250]] হলে আউটপুট ৩৫০, কারণ [1,2,100] এবং [2,100,250] নিলে ১০০+২৫০=৩৫০।

সমাধানের পদ্ধতি (DP + কোঅর্ডিনেট কম্প্রেশন / টাইম-বেজড DP)

d = এন্ড টাইম -> [(start, profit)] ম্যাপ।
n = সর্বোচ্চ এন্ড টাইম।
A = আকার n+1 এর অ্যারে, সব ০।
end = 0..n লুপ:
- যদি end in d: প্রতিটি (start, profit) এর জন্য 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] * (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]]