Arrange for the Busiest Ranges

Medium

You get an array of non-negative integers values and a list of ranges ranges, where ranges[i] = [l, r] covers indices l through r inclusive (0-based). You may rearrange the elements of values in any order. After that, each range contributes the sum of the elements at its positions, and all these sums are added together. Return the largest possible total modulo 10⁹ + 7.

Example 1

values=[1, 5, 2], ranges=[[0, 1], [1, 2]] → 13

Position 1 lies in both ranges, so 5 goes there. For example, [2, 5, 1]: (2 + 5) + (5 + 1) = 13.

Example 2

values=[4, 0, 7, 3], ranges=[[2, 2], [0, 3], [2, 3]] → 32

Position 2 is covered three times, position 3 twice, the rest once. 7 · 3 + 4 · 2 + 3 + 0 = 32.

Example 3

values=[9], ranges=[[0, 0], [0, 0]] → 18

The same range is asked twice: 9 + 9 = 18.

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i] ≤ 10⁵
1 ≤ len(ranges) ≤ 10⁵
ranges[i] = [l, r], 0 ≤ l ≤ r < len(values)

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Prefix Sum Sorting

Similar problems

Studios for Recording Sessions Medium Even Out With Increments Medium Level the Jars Medium Rug Over Painted Stretches Medium Fewest Rooms for the Bookings Medium

Input

values=[1, 5, 2], ranges=[[0, 1], [1, 2]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 92 tests on the server, hidden ones included.