[Leetcode]1589. Maximum Sum Obtained of Any Permutation

We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The ith request asks for the sum of nums[starti] + nums[starti + 1] + ... + nums[endi - 1] + nums[endi]. Both starti and endi are 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.

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)

Reference

• https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/
• https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/discuss/854206/JavaC%2B%2BPython-Sweep-Line
• https://en.wikipedia.org/wiki/Prefix_sum