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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3

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

1
2
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

  1. Create a frequency array to count how many times each index is requested using a prefix sum trick.
  2. For each request [start, end], increment freq[start] and decrement freq[end+1].
  3. Compute the prefix sum of freq to get the total count for each index.
  4. Sort freq and nums in descending order.
  5. 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxSumRangeQuery(vector<int>& nums, vector<vector<int>>& requests) {
        int n = nums.size(), mod = 1e9+7;
        vector<int> freq(n+1);
        for (auto& req : requests) {
            freq[req[0]]++;
            freq[req[1]+1]--;
        }
        for (int i = 1; i < n; ++i) freq[i] += freq[i-1];
        freq.pop_back();
        sort(nums.rbegin(), nums.rend());
        sort(freq.rbegin(), freq.rend());
        long ans = 0;
        for (int i = 0; i < n; ++i) ans = (ans + 1L * nums[i] * freq[i]) % mod;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maxSumRangeQuery(nums []int, requests [][]int) int {
    n, mod := len(nums), int(1e9+7)
    freq := make([]int, n+1)
    for _, req := range requests {
        freq[req[0]]++
        freq[req[1]+1]--
    }
    for i := 1; i < n; i++ { freq[i] += freq[i-1] }
    freq = freq[:n]
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))
    sort.Sort(sort.Reverse(sort.IntSlice(freq)))
    ans := 0
    for i := 0; i < n; i++ {
        ans = (ans + nums[i]*freq[i]) % mod
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length, mod = (int)1e9+7;
        int[] freq = new int[n+1];
        for (int[] req : requests) {
            freq[req[0]]++;
            freq[req[1]+1]--;
        }
        for (int i = 1; i < n; ++i) freq[i] += freq[i-1];
        freq = Arrays.copyOf(freq, n);
        Arrays.sort(nums);
        Arrays.sort(freq);
        long ans = 0;
        for (int i = n-1; i >= 0; --i) ans = (ans + 1L * nums[i] * freq[i]) % mod;
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    fun maxSumRangeQuery(nums: IntArray, requests: Array<IntArray>): Int {
        val n = nums.size
        val mod = 1_000_000_007
        val freq = IntArray(n+1)
        for (req in requests) {
            freq[req[0]]++
            freq[req[1]+1]--
        }
        for (i in 1 until n) freq[i] += freq[i-1]
        val freqArr = freq.sliceArray(0 until n)
        nums.sortDescending()
        freqArr.sortDescending()
        var ans = 0L
        for (i in 0 until n) ans = (ans + nums[i].toLong() * freqArr[i]) % mod
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def max_sum_range_query(nums: list[int], requests: list[list[int]]) -> int:
    n, mod = len(nums), 10**9+7
    freq = [0] * (n+1)
    for s, e in requests:
        freq[s] += 1
        freq[e+1] -= 1
    for i in range(1, n):
        freq[i] += freq[i-1]
    freq.pop()
    nums.sort(reverse=True)
    freq.sort(reverse=True)
    ans = sum(x*y for x, y in zip(nums, freq)) % mod
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn max_sum_range_query(nums: Vec<i32>, requests: Vec<Vec<i32>>) -> i32 {
        let n = nums.len();
        let mut freq = vec![0; n+1];
        for req in &requests {
            freq[req[0] as usize] += 1;
            freq[req[1] as usize + 1] -= 1;
        }
        for i in 1..n { freq[i] += freq[i-1]; }
        freq.pop();
        let mut nums = nums;
        nums.sort_by(|a, b| b.cmp(a));
        freq.sort_by(|a, b| b.cmp(a));
        let mut ans: i64 = 0;
        for i in 0..n {
            ans = (ans + nums[i] as i64 * freq[i] as i64) % 1_000_000_007;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maxSumRangeQuery(nums: number[], requests: number[][]): number {
        const n = nums.length, mod = 1e9+7;
        const freq = Array(n+1).fill(0);
        for (const [s, e] of requests) {
            freq[s]++;
            freq[e+1]--;
        }
        for (let i = 1; i < n; ++i) freq[i] += freq[i-1];
        freq.pop();
        nums.sort((a, b) => b - a);
        freq.sort((a, b) => b - a);
        let ans = 0;
        for (let i = 0; i < n; ++i) ans = (ans + nums[i] * freq[i]) % mod;
        return ans;
    }
}