โปรแกรมหาผลรวมสูงสุดของ permutation ใดๆ จาก requests ใน Python

ปัญหา

อาร์เรย์ nums และ requests[i] = [start_i, end_i] ขอผลรวม nums[start_i..end_i] จัดเรียง nums ใหม่ (permutation) ให้ผลรวมของทุก request รวมกันสูงสุด modulo 1e9+7

ตัวอย่าง

nums=[10,20,30,40,50], requests=[[1,3],[0,1]] → 190 (เรียง [30,50,40,20,10] request0: 50+40+20=110, request1: 30+50=80 รวม 190)

ขั้นตอนการแก้ปัญหา

1. สร้าง event list A: (start, 0) และ (end, 1) สำหรับแต่ละ request
2. เรียง A
3. Sweep line คำนวณความถี่แต่ละดัชนี fr[count] = list of (start, end)
4. เรียง nums มากไปน้อย
5. จับคู่ค่ามากกับความถี่มาก: ans += sum(nums[i:i+d]) * k
6. คืน ans % (10^9+7)

การนำไปใช้งาน (Python)

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 = sorted(fr.keys(), 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]]

เอาต์พุต

190