1589. 所有排列中的最大和.md

1589. 所有排列中的最大和

• 差分数据 + 排序 + 哈希表

function maxSumRangeQuery(nums: number[], requests: number[][]): number {

    const times: number[] = new Array(nums.length + 1).fill(null),
        MOD: number = 10 ** 9 + 7;

    for (const [start, end] of requests) {
        times[start] += 1;
        times[end + 1] -= 1;
    }

    for (let i = 1; i < nums.length; i++) {
        times[i] += times[i - 1];
    }

    nums.sort((a, b) => b - a);
    times.sort((a, b) => b - a);

    let sum = 0;

    for (let i = 0; i < nums.length; ++i) {
        sum += nums[i] * times[i];
    }

    return sum % MOD;
};