Maximum Sum Obtained of Any Permutation
We have an array of integers, nums, and an array of requests where requests[i] = [starti, endi]. The i^th 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 10^9 + 7.
Example 1
Input
nums = [1,2,3,4,5], requests = [[1,3],[0,1]]Output
19A permutation with total sum 19 is best among all permutations of nums.
Example 2
Input
nums = [1,2,3,4,5,6], requests = [[0,1]]Output
11A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].
Constraints
- n == nums.length
- 1 <= n <= 10^5
- 0 <= nums[i] <= 10^5
- 1 <= requests.length <= 10^5
- requests[i].length == 2
- 0 <= starti <= endi < n