Max total of k consecutive bags over disjoint valued segments, modulo 1e9+7
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
Bags stand in a single row that never ends, one bag at every positive integer position `1, 2, 3, ...`. You are given `segments`, where `segments[i] = [l, r, v]` means that every bag at a position from `l` to `r` inclusive holds `v` units of money. No two segments share a position, and every bag that no segment covers is empty and holds `0`.
Choose `k` consecutive bags, meaning the bags at positions `s, s + 1, ..., s + k - 1` for some start `s >= 1`. Let `M` be the largest total amount of money any such choice collects. Return `M` modulo `1,000,000,007`.
### Function Signature
```python
def max_k_consecutive_bags(k: int, segments: list[list[int]]) -> int:
```
### Rules
- The chosen positions must be consecutive. They may include empty bags, and they may cover a segment only partly: every covered bag of a segment contributes its full `v`, and the uncovered bags of that segment contribute nothing.
- `segments` may be given in any order. Two segments may be adjacent (one ends at `p` and another starts at `p + 1`), but they never overlap.
- Compare the exact, unreduced totals to find `M`, and apply the modulo only to `M`. A larger exact total can leave a smaller remainder, as Example 3 shows.
- The return value is a single integer, so it does not matter which start `s` achieves `M`.
### Constraints
- `1 <= n <= 200,000`, where `n = len(segments)`
- `1 <= l <= r <= 10^9` for every segment
- `1 <= v <= 10^6` for every segment
- `1 <= k <= 10^9`, and `k` may exceed the distance spanned by all the segments together
- Positions and `k` fit in a 32-bit signed integer, but an exact total can reach `10^9 * 10^6 = 10^15`, which is beyond `2^31 - 1`. Every exact total stays below `2^53`, and the returned value is below `1,000,000,007`.
### Examples
**Example 1**
```text
Input: k = 5, segments = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
Output: 16
```
Positions `3` through `7` hold `2, 2, 0, 5, 7`, which sums to `16`. No other five consecutive bags collect more, and `16` is already below the modulus.
**Example 2**
```text
Input: k = 5, segments = [[10, 12, 4], [3, 5, 1], [7, 8, 6]]
Output: 20
```
The segments arrive unsorted. Positions `7` through `11` hold `6, 6, 0, 4, 4`, a total of `20`: both bags of `[7, 8, 6]`, the empty bag at position `9`, and only the first two bags of `[10, 12, 4]`.
**Example 3**
```text
Input: k = 1012, segments = [[1, 1000, 1000000], [1001, 1012, 1], [5001, 6012, 988000]]
Output: 5
```
Positions `1` through `1012` collect `1000 * 1,000,000 + 12 * 1 = 1,000,000,012`, the largest exact total, so `M = 1,000,000,012` and the answer is `M` modulo `1,000,000,007`, which is `5`. Positions `5001` through `6012` collect only `1012 * 988,000 = 999,856,000`. Its remainder is larger, but its exact total is smaller, so it does not decide the answer.
Overview: Disjoint segments [l, r, v] give every bag from position l to r the value v, and all other bags in an endless row are empty. Find the largest total over k consecutive bags, returned modulo 1,000,000,007, when k and positions reach 10^9, testing window sums over sparse ranges that cut through segments.
Read the full Amazon Software Engineer interview experience this question came from
Bags stand in a single row that never ends, one bag at every positive integer position `1, 2, 3, ...`. You are given an integer `k` and a list `segments`, where `segments[i] = [l, r, v]` means that every bag at a position from `l` to `r` inclusive holds `v` units of money. No two segments share a position, and every bag that no segment covers is empty and holds `0`.
Choose `k` consecutive bags, that is, the bags at positions `s, s + 1, ..., s + k - 1` for some start `s >= 1`. Let `M` be the largest total amount of money any such choice collects. Return `M` modulo `1,000,000,007`.
### Rules
- The chosen positions must be consecutive. They may include empty bags, and they may cover a segment only partly: every chosen bag of a segment contributes its full `v`, and the unchosen bags of that segment contribute nothing.
- `segments` may be given in any order. Two segments may be adjacent (one ends at `p` and another starts at `p + 1`), but they never overlap.
- Compare the exact, unreduced totals to find `M`, and apply the modulo only to `M`. A larger exact total can leave a smaller remainder, as Example 2 shows.
- The return value is a single integer, so it does not matter which start `s` achieves `M`.
### Constraints
- `1 <= n <= 200,000`, where `n = len(segments)`
- `1 <= l <= r <= 10^9` for every segment
- `1 <= v <= 10^6` for every segment
- `1 <= k <= 10^9`, and `k` may exceed the distance spanned by all the segments together
- Positions and `k` fit in a 32-bit signed integer, but an exact total can reach `10^9 * 10^6 = 10^15`, which exceeds `2^31 - 1`, so accumulate totals in a 64-bit integer (`long` in Java, `long long` in C++). Every exact total stays below `2^53`, and the returned value is below `1,000,000,007`, so it fits in a 32-bit `int`.
### Example 1
```text
Input: k = 5, segments = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
Output: 16
```
Positions `3` through `7` hold `2, 2, 0, 5, 7`, which sums to `16`. No other five consecutive bags collect more, and `16` is already below the modulus.
### Example 2
```text
Input: k = 1012, segments = [[1, 1000, 1000000], [1001, 1012, 1], [5001, 6012, 988000]]
Output: 5
```
Positions `1` through `1012` collect `1000 * 1,000,000 + 12 * 1 = 1,000,000,012`, the largest exact total, so `M = 1,000,000,012` and the answer is `M` modulo `1,000,000,007`, which is `5`. Positions `5001` through `6012` collect only `1012 * 988,000 = 999,856,000`. Its remainder is larger, but its exact total is smaller, so it does not decide the answer.
Constraints
- 1 <= n <= 200,000, where n = len(segments)
- 1 <= l <= r <= 10^9 for every segment
- 1 <= v <= 10^6 for every segment
- 1 <= k <= 10^9, and k may exceed the distance spanned by all the segments together
- No two segments share a position; segments may be given in any order, and two segments may be adjacent
- Positions and k fit in a 32-bit signed integer, but an exact total can reach 10^9 * 10^6 = 10^15, beyond 2^31 - 1 (use long in Java, long long in C++); every exact total stays below 2^53, and the returned value is below 1,000,000,007
Examples
Input: (5, [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]])
Expected Output: 16
Explanation: Source Example 1: positions 3..7 hold 2, 2, 0, 5, 7 for 16; adjacent segments [6,6] and [7,7] next to gaps.
Input: (5, [[10, 12, 4], [3, 5, 1], [7, 8, 6]])
Expected Output: 20
Explanation: Source Example 2: unsorted segments; positions 7..11 hold 6, 6, 0, 4, 4 = 20, covering [10, 12, 4] only partly.
Hints
- Positions and k go up to 10^9, so you cannot walk the row bag by bag. Work with the segments themselves.
- When a window slides one bag to the right, its total changes by the bag it gains minus the bag it loses. Ask where that change can switch sign.
- Pick M by comparing exact totals, which can reach 10^15, and apply the modulo only to M.