We have an array of integers,`nums`

, and an array of`requests`

where`requests[i] = [start`

. The_{i}, end_{i}]`i`

request asks for the sum of^{th}`nums[start`

. Both_{i}] + nums[start_{i}+ 1] + ... + nums[end_{i}- 1] + nums[end_{i}]`start`

and_{i}`end`

are_{i}0-indexed. Returnthe maximum total sum of all requestsamong all permutationsof`nums`

. Since the answer may be too large, return itmodulo`10`

.^{9}+ 7

## Logic

To maximize the total sum, we can simply assign the larger weights to elements that are requested more frequently. The brute force approach could be implementing an array `cnt`

of size `n=len(nums)`

and for each request `requests[i]=[start,end]`

, we increase each element in `nums[start:end+1]`

by 1. Finally the values stored in `cnt`

would be the frequencies.

However, that would result in O(n^2) time complexity in the worst cases. To achieve O(n), we can apply a small trick here. We don’t have to increase every element in `nums[start:end+1]`

for `requests[i]=[start,end]`

, in fact, we can only increase the element at the `start`

and the `end`

. And after processing all requests, we can scan the `cnt`

and the prefix sum would be the frequencies.

Note that for all intervals inputs, this method should be the first intuition you come up with.

@lee215 from Leetcode

## Code

class Solution: def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int: n = len(nums) cnt = [0]*(n+1) for s,e in requests: cnt[s] += 1 cnt[e+1] -= 1 for i in range(1,n): cnt[i] += cnt[i-1] return sum(a*b for a,b in zip(sorted(cnt[:-1]),sorted(nums))) % (10**9+7)