Show problems as
Classic problem #3413MediumArrayBinary SearchGreedySliding WindowSortingPrefix Sum

Maximum Coins From K Consecutive Bags

Real-world version: Richest Run of Consecutive Bins
Tracked in this browser only
Read Maximum Coins From K Consecutive Bags on LeetCode(opens in a new tab)

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

A picking aisle has bins at every whole position 1, 2, 3, ... running away from the door. The stock is recorded in stretches: runs[i] = [from, to, per] means every bin at a position from from to to inclusive holds exactly per items. No two stretches cover the same position, and a position no stretch mentions holds nothing.

A picker is sent down the aisle to clear span bins standing next to each other, that is span consecutive positions, all of them at position 1 or beyond. Return the largest number of items such a group of bins can hold.

Examples

Example 1

Input
runs = [[2, 5, 3], [8, 9, 10]], span = 4
Output
20

Clearing positions 6 through 9 picks up nothing at 6 and 7 and 10 items at each of 8 and 9, for 20 items.

Example 2

Input
runs = [[1, 10, 1], [11, 12, 100]], span = 3
Output
201

Clearing positions 10, 11 and 12 picks up 1 item at position 10 and 100 at each of 11 and 12, for 201 items.

Example 3

Input
runs = [[5, 5, 7]], span = 3
Output
7

Only position 5 holds anything, so any group of three bins covering it, such as positions 4, 5 and 6, picks up 7 items.

Constraints

  • 1 <= runs.length <= 10^5
  • 1 <= span <= 10^9
  • runs[i].length == 3
  • 1 <= runs[i][0] <= runs[i][1] <= 10^9
  • 1 <= runs[i][2] <= 1000
  • The stretches do not overlap.
  • The answer is at most span * 1000, so it stays below 10^12.

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 richest_run(runs: list[list[int]], span: int) -> int:
Java
public long richestRun(int[][] runs, int span)

More on the same topics