1589. Maximum Sum Obtained of Any Permutation¶
题目信息¶
- 题号:
1589
- 难度:
Medium
- 主题:
数组、差分、排序、贪心
- 原题:
- 重点:
可以任意重排
nums;每个下标被请求覆盖的次数越多,应分配越大的元素
题目重述¶
给定整数数组 nums 和若干闭区间请求 requests[i] = [start_i,end_i]。可以先任意重排 nums,随后计算每个请求区间内的元素和,并把所有请求结果相加。
请返回能够得到的最大总和,对 10^9 + 7 取模。
1 <= nums.length <= 10^5,请求数量不超过 10^5,所有区间下标合法。
自建示例¶
高频下标应放置最大元素:
输入:nums = [1,2,3], requests = [[0,1],[1,2]]
输出:9
解释:下标覆盖次数为 [1,2,1],把 3 放在中间,可得到 4+5=9。
只有整段请求时排列不影响结果:
输入:nums = [4,1], requests = [[0,1]]
输出:5
解释:请求覆盖全部元素,任意排列的总和都为 5。