Show problems as
Classic problem #1589MediumArrayGreedySortingPrefix Sum

Maximum Sum Obtained of Any Permutation

Real-world version: Best Order for Repeated Scans
Tracked in this browser only
Read Maximum Sum Obtained of Any Permutation on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A belt has n slots. The parcel weights are given as nums, and you may load them onto the belt in any order, one weight per slot.

Each entry of requests is a pair [start, end] naming a stretch of slots, ends included. A scan of that stretch reports the total weight sitting in it.

Choose the loading order that makes the totals reported by all the scans add up to as much as possible, and return that sum modulo 10^9 + 7.

Examples

Example 1

Input
nums = [7, 12, 3, 20, 9], requests = [[0, 2], [1, 4], [2, 3]]
Output
112

The three stretches cover the slots 1, 2, 3, 2, 1 times from left to right. Loading 3, 9, 20, 12, 7 puts the heaviest parcel in the most-scanned slot, and the three scans then report 32, 48 and 32.

Example 2

Input
nums = [8, 15, 22], requests = [[0, 1], [0, 1], [0, 1], [2, 2]]
Output
119

The first two slots are scanned three times each and the last only once, so the lightest parcel goes at the end. The scans then report 37 three times and 8 once.

Example 3

Input
nums = [0, 0, 0], requests = [[0, 2], [1, 1]]
Output
0

Every parcel weighs nothing, so no order beats any other.

Constraints

  • nums.length == n
  • 1 <= n <= 10^5
  • 0 <= nums[i] <= 10^5
  • 1 <= requests.length <= 10^5
  • requests[i].length == 2
  • 0 <= requests[i][0] <= requests[i][1] <= n - 1

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_sum_range_query(nums: list[int], requests: list[list[int]]) -> int:
Java
public int maxSumRangeQuery(int[] nums, int[][] requests)

More on the same topics