Maximize a Fixed-Length Sum over Sparse Constant Segments
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Online Assessment
# Maximize a Fixed-Length Sum over Sparse Constant Segments
Positive integer positions represent bags arranged from 1 to infinity. You are given non-overlapping closed segments. A segment `[left, right, value]` means every bag from `left` through `right` contains `value` units of money. Bags outside all segments contain zero.
Choose exactly `k` consecutive bags and maximize their total money. Compute the maximum using the full integer values, then return that maximum modulo `1,000,000,007`.
Implement:
```text
calculateMaximumConsecutiveSum(k, segments) -> integer
```
Segments may be supplied in any order. They never intersect, and every value is positive.
## Constraints
- `1 <= segments.length <= 200,000`
- `1 <= k <= 10^9`
- `1 <= left <= right <= 10^9`
- `1 <= value <= 10^6`
## Examples
### Example 1
```text
k = 5
segments = [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]]
output = 16
```
The window from bag 3 through bag 7 contains `2 + 2 + 0 + 5 + 7 = 16`.
### Example 2
```text
k = 3
segments = [[5, 7, 4], [2, 2, 10]]
output = 12
```
The window from bag 5 through bag 7 contains 12, which is greater than any length-three window containing bag 2.
Overview: Find the maximum sum of exactly k consecutive positions in an effectively infinite sparse array represented by non-overlapping constant-value segments. The prompt preserves large coordinate bounds, arbitrary segment order, zero-filled gaps, full-value maximization, and final modulo output.
Read the full Amazon Software Engineer interview experience this question came from
Implement calculateMaximumConsecutiveSum(k, segments). Positive integer bag positions start at 1 and continue without bound. Each non-overlapping closed segment [left, right, value] gives every bag in that range the positive value; all other bags contain zero. Segments may be in any order. Choose exactly k consecutive bags, maximize their sum using the full integer values, and only then return that maximum modulo 1,000,000,007.
Constraints
- 1 <= segments.length <= 200,000
- 1 <= k <= 10^9
- Every segment is [left, right, value] with 1 <= left <= right <= 10^9.
- Segments are pairwise non-overlapping and may be supplied in any order.
- 1 <= value <= 10^6; bags outside all segments contain zero.
- Choose exactly k consecutive positive-integer bag positions.
- Maximize with full integer values before returning modulo 1,000,000,007.
Examples
Input: (5, [[1, 4, 2], [6, 6, 5], [7, 7, 7], [9, 10, 1]])
Expected Output: 16
Explanation: The first source example selects bags 3 through 7 across a gap and three segments.
Input: (3, [[5, 7, 4], [2, 2, 10]])
Expected Output: 12
Explanation: The second source example favors the complete length-three segment.
Hints
- Compare two adjacent windows: one bag leaves at x and one enters at x + k.
- A constant range in the bag values becomes a constant range in the adjacent-window difference.