We have an array of integers,
nums, and an array of
requests[i] = [starti, endi]. The
ithrequest asks for the sum of
nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both
endiare 0-indexed. Return the maximum total sum of all requests among all permutations of
nums. Since the answer may be too large, return it modulo
109 + 7.
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
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
class Solution: def maxSumRangeQuery(self, nums: List[int], requests: List[List[int]]) -> int: n = len(nums) cnt = *(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)