1d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:T1d4e,

Problem

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 requestsamong all permutations of nums.

Since the answer may be too large, return it modulo 10^9 + 7.

Examples

Example 1

Input: nums = [1,2,3,4,5], requests = [[1,3],[0,1]]
Output: 19
Explanation: One permutation of nums is [2,1,3,4,5] with the following result: 
requests[0] -> nums[1] + nums[2] + nums[3] = 1 + 3 + 4 = 8
requests[1] -> nums[0] + nums[1] = 2 + 1 = 3
Total sum: 8 + 3 = 11.
A permutation with a higher total sum is [3,5,4,2,1] with the following result:
requests[0] -> nums[1] + nums[2] + nums[3] = 5 + 4 + 2 = 11
requests[1] -> nums[0] + nums[1] = 3 + 5  = 8
Total sum: 11 + 8 = 19, which is the best that you can do.

Example 2

Input: nums = [1,2,3,4,5,6], requests = [[0,1]]
Output: 11
Explanation: A permutation with the max total sum is [6,5,4,3,2,1] with request sums [11].

Example 3

Input: nums = [1,2,3,4,5,10], requests = [[0,2],[1,3],[1,1]]
Output: 47
Explanation: A permutation with the max total sum is [4,10,5,3,2,1] with request sums [19,18,10].

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

Solution

Method 1 – Greedy with Frequency Counting

Intuition

To maximize the sum of all requests, we should assign the largest numbers in nums to the indices that are requested most often. By counting how many times each index is requested, sorting these counts, and matching the largest numbers to the most requested indices, we maximize the total sum.

Approach

Create a frequency array to count how many times each index is requested using a prefix sum trick.
For each request [start, end], increment freq[start] and decrement freq[end+1].
Compute the prefix sum of freq to get the total count for each index.
Sort freq and nums in descending order.
Multiply corresponding elements and sum them up, then return the result modulo 10^9 + 7.

Complexity

⏰ Time complexity: O(n + r + n log n) — Counting is O(r), sorting is O(n log n), summing is O(n).
🧺 Space complexity: O(n) — For frequency array.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {\n

Related Tags