BinarySearch 0926 Permute List to Make Largest Range Sum

Problem statement

https://binarysearch.com/problems/Permute-List-to-Make-Largest-Range-Sum/

Solution

Equal to Leetcode 1589. Maximum Sum Obtained of Any Permutation.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, Q):
        n = len(nums)
        diff = [0] * (n + 1)
        for x, y in Q:
            diff[x] += 1
            diff[y + 1] -= 1
            
        acc = list(accumulate(diff))[:-1]
        return sum(x*y for x, y in zip(sorted(acc), sorted(nums))) % (10**9 + 7)