LeetCode 1589: Maximum Sum Obtained of Any Permutation

Explanation

To solve this problem, we need to find the maximum sum obtained by any permutation of the given nums array based on the given requests. We can achieve this by considering the frequency of each index in the requests and then sorting both the nums array and the request indices. By iteratively distributing the values from the largest to smallest elements in the nums array to the requested indices, we can find the maximum total sum.

1. Calculate the frequency of each index in the requests.
2. Sort both the nums array and the requests based on the values.
3. Iterate through the sorted nums array and update the requested indices with the maximum values.
4. Calculate the total sum based on the updated requests.

Time complexity: O(n log n) where n is the number of elements in the nums array. Space complexity: O(n) for storing the frequency of indices.

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        int n = nums.length;
        int[] freq = new int[n];
        for (int[] request : requests) {
            freq[request[0]]++;
            if (request[1] + 1 < n) {
                freq[request[1] + 1]--;
            }
        }
        for (int i = 1; i < n; i++) {
            freq[i] += freq[i - 1];
        }

        Arrays.sort(nums);
        Arrays.sort(freq);

        long result = 0;
        int mod = 1000000007;
        for (int i = 0; i < n; i++) {
            result = (result + (long) nums[i] * freq[i]) % mod;
        }

        return (int) result;
    }
}