We have an array of integers,nums
, and an array ofrequests
whererequests[i] = [starti, endi]
. Theith
request asks for the sum ofnums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]
. Bothstarti
andendi
are 0-indexed. Return the maximum total sum of all requests among all permutations ofnums
. Since the answer may be too large, return it modulo109 + 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)