পাইথনে পারমুটেশন থেকে রিকোয়েস্টের সর্বোচ্চ সম বের করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে nums এবং আরেকটি অ্যারে requests যেখানে requests[i] = [start_i, end_i] মানে i-তম রিকোয়েস্ট চায় nums[start_i] + ... + nums[end_i] এর সম। সব পারমুটেশনের মধ্যে রিকোয়েস্টগুলোর মোট সম সর্বোচ্চ কত হবে সেটি বের করতে হবে। উত্তর বড় হলে 10^9+7 দিয়ে মডুলো রিটার্ন করুন।

যেমন, ইনপুট হলে nums = [10,20,30,40,50], requests = [[1,3],[0,1]], তবে আউটপুট হবে 190 কারণ [30,50,40,20,10] আকারে সাজালে: রিকোয়েস্ট ০: 50+40+20=110, রিকোয়েস্ট ১: 30+50=80, মোট 190।

সমাধানের ধাপসমূহ

A := []
requests-এ প্রতিটি (s,e) এর জন্য: A.append((s,0)), A.append((e,1))
A.sort()
fr := ডিফল্টডিক্ট(লিস্ট), cnt := 0, n := len(A), i := 0
i < n থাকা পর্যন্ত লুপ চালান (ইভেন্ট প্রসেস করে ফ্রিকোয়েন্সি বের করুন)।
nums রিভার্স সর্ট করুন।
ks := sorted(fr.keys(), reverse=True)
ans := 0, m := 10**9+7, i := 0
প্রতিটি k in ks এবং fr[k]-এ প্রতিটি (s,e) এর জন্য:
- d := e-s+1
- ans += sum(nums[i:i+d]) * k, ans %= m, i += d
ans রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

from collections import defaultdict
def solve(nums, requests):
    A = []
    for s, e in requests:
        A.append((s, 0))
        A.append((e, 1))
    A.sort()
    fr = defaultdict(list)
    cnt = 0
    n = len(A)
    i = 0
    while i < n:
        r = 1
        while i < n - 1 and A[i+1] == A[i]:
            r += 1
            i += 1
        p, flag = A[i]
        if flag == 0:
            cnt += r
            if cnt - r > 0:
                fr[cnt-r].append((pre, p-1))
            pre = p
        elif flag == 1:
            cnt -= r
            fr[cnt+r].append((pre, p))
            pre = p+1
        i += 1
    nums.sort(reverse=True)
    ks = list(fr.keys())
    ks.sort(reverse=True)
    ans = 0
    m = 10**9 + 7
    i = 0
    for k in ks:
        for s, e in fr[k]:
            d = e - s + 1
            ans += sum(nums[i:i+d]) * k
            ans %= m
            i += d
    return ans

nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))

ইনপুট

[10,20,30,40,50],[[1,3],[0,1]]