# 1589. Maximum Sum Obtained of Any Permutation
###### tags: `Leetcode` `Medium` `Line Sweep`
Link: https://leetcode.com/problems/maximum-sum-obtained-of-any-permutation/
## 思路
先用差分法找出每个idx用了几次 放在line array里
然后按照用的次数从大到小 分配上从大到小的数字即可
## Code

class Solution {
    public int maxSumRangeQuery(int[] nums, int[][] requests) {
        Arrays.sort(nums);
        int[] line = new int[100002];
        for(int[] request:requests){
            line[request[0]]+=1;
            line[request[1]+1]-=1;
        }
        for(int i=1; i<line.length; i++){
            line[i] += line[i-1];
        }
        Arrays.sort(line);
        long ans = 0;
        int mod = 1000000007;
        int idx = nums.length-1;
        
        for(int i=line.length-1; i>=0; i--){
            if(line[i]==0) break;
            ans = (ans+line[i]*(long)nums[idx--])%mod;
        }
        
        return (int)(ans%mod);
    }
}