Chương trình tìm tổng lớn nhất của các yêu cầu trên hoán vị trong Python

Cho mảng nums và requests (mỗi request [start, end] yêu cầu tổng đoạn). Hoán vị nums để tối đa hóa tổng tất cả requests. Trả về modulo 10⁹+7.

Ví dụ: nums=[10,20,30,40,50], requests=[[1,3],[0,1]] → 190. Sắp xếp: [30,50,40,20,10]. Request 0: 50+40+20=110, Request 1: 30+50=80, tổng=190.

Giải thuật (Tần suất vị trí + Sắp xếp)

1. Mảng A lưu sự kiện: (start, 0) mở, (end, 1) đóng.
2. Sắp xếp A, quét tính tần suất mỗi vị trí được yêu cầu (fr[count] lưu các đoạn có tần suất = count).
3. Sắp xếp nums giảm dần.
4. Gán số lớn nhất cho vị trí tần suất cao nhất: duyệt count giảm, cộng sum(nums[i:i+d]) * count.

Ví dụ minh họa

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
    pre = 0
    flag = 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))

Đầu vào

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

Đầu ra

190