0881MediumArrayGreedySortingPrefix Sum

Best Order for Repeated Scans

Tracked in this browser only

Trains the technique from

LeetCode 1589Maximum Sum Obtained of Any Permutation

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_sum_range_query(nums: list[int], requests: list[list[int]]) -> int:

Java

public int maxSumRangeQuery(int[] nums, int[][] requests)

The intended approach

Time O(n log n + q) for n slots and q scans: the difference array is linear and the sort dominates.Space O(n) for the coverage counts.

Every scan contributes the weights of the slots it covers, so a slot covered by `c` scans contributes its weight `c` times. The order only decides which weight lands in which slot, so the total is the coverage counts multiplied against the weights and added up, and pairing the heaviest parcel with the most-scanned slot maximises that. Exchanging any two assignments where a heavier parcel sits in a less-scanned slot never loses, which is why sorting both sides and pairing them off is optimal. Coverage counts come from one difference array: add one at each stretch's start and subtract one just past its end, then take a running total. Sort the counts and the weights, pair them largest with largest, and reduce only at the end.

Pythonentry point: max_sum_range_query

def max_sum_range_query(nums, requests):
    n = len(nums)
    delta = [0] * (n + 1)
    for start, end in requests:
        delta[start] += 1
        delta[end + 1] -= 1
    counts = [0] * n
    running = 0
    for i in range(n):
        running += delta[i]
        counts[i] = running
    counts.sort()
    order = sorted(nums)
    total = 0
    for i in range(n):
        total += counts[i] * order[i]
    return total % 1000000007

The obvious version

Try every loading order of the parcels, add up what each scan would report, and keep the largest total. Factorial in the slot count and it never reasons about coverage at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_sum_range_query(nums, requests):
    import itertools
    n = len(nums)
    best = 0
    for order in itertools.permutations(nums):
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + order[i]
        total = 0
        for start, end in requests:
            total += prefix[end + 1] - prefix[start]
        if total > best:
            best = total
    return best % 1000000007

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in