LeetCode 1589. Maximum Sum Obtained of Any Permutation

看到排列先嚇到一次，看內文又嚇一次，還以為要線段樹。

題目

requests表示好幾個區間，在nums所有可能排列下，求出所有區間和最大值。
答案必須mod 10^9+7。

解法

本想雙迴圈暴力計算每個位置的出現次數，看到測資n<=10^5直接放棄。
使用psum陣列，在每個區間起點+1，終點後-1，做前綴和則可得到每個位置權重。
最後將psum和nums排序，相乘後相加即可。

requests = [[0,2],[1,3],[1,1]]
psum = [1,3,2,1,0]

class Solution:
    def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int:
        N = len(nums)
        psum = [0]*N
        for start, end in requests:
            psum[start] += 1
            if end+1 < N:
                psum[end+1] -= 1

        for i in range(1, N):
            psum[i] += psum[i-1]

        nums.sort()
        psum.sort()

        return sum([nums[i]*psum[i] for i in range(N)]) % (10**9+7)