Maximize Revenue With Two Contiguous Delivery Routes
Company: Nuro
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Houses lie in a line. `values[i]` is the nonnegative payment for delivering to house `i`. Two delivery robots are available. Robot one can serve at most `c1` consecutive houses, and robot two can serve at most `c2` consecutive houses. Their routes must not overlap.
Implement `max_delivery_revenue(values, c1, c2)` and return the maximum total payment. A robot may serve fewer than its capacity, and a robot with zero capacity serves no houses.
## Constraints
- `1 <= len(values) <= 200,000`
- `0 <= values[i] <= 10^9`
- `0 <= c1, c2 <= len(values)`
- Each chosen route is one contiguous segment.
- The answer may exceed 32-bit range.
## Examples
`values = [4, 2, 3, 5]`, `c1 = 2`, `c2 = 1` returns `12`. One robot serves `[3, 5]` and the other serves `[4]`.
`values = [8, 1, 1]`, `c1 = 1`, `c2 = 1` returns `9`.
## Clarifications
The robots may appear in either left-to-right order. Because payments are nonnegative, using fewer than the available capacity is only useful when boundaries or the other route prevent a longer segment.
## Hint
Precompute the best bounded-length route available entirely to the left and entirely to the right of each split. Evaluate both assignments of capacities to the two sides.
## Interview Follow-ups
- Return both selected route ranges.
- Generalize to `k` robots with different capacities.
- Discuss the change when house payments may be negative.
Quick Answer: Maximize delivery revenue from two nonoverlapping contiguous routes whose lengths are bounded by separate robot capacities. Cover either left-to-right ordering, zero capacities, nonnegative payments, large totals, range reconstruction, more robots, and the variant where payments may be negative.
Houses are arranged in a line, and `values[i]` is the nonnegative payment for delivering to house `i`. Robot one may serve at most `c1` consecutive houses and robot two may serve at most `c2` consecutive houses. Their contiguous routes must not overlap. Implement `max_delivery_revenue(values, c1, c2)` and return the greatest total payment. A robot may serve fewer houses than its capacity, and a robot whose capacity is zero serves no houses. The robots may occur in either left-to-right order.
Constraints
- 1 <= len(values) <= 200,000
- 0 <= values[i] <= 10^9
- 0 <= c1, c2 <= len(values)
- Each robot chooses at most one contiguous segment.
- The two chosen routes must not overlap.
- The answer is at most 200,000,000,000,000, fits signed 64-bit arithmetic, and may exceed 32-bit range.
Examples
Input: ([3], 0, 0)
Expected Output: 0
Explanation: Both zero-capacity robots must choose empty routes.
Input: ([11], 1, 0)
Expected Output: 11
Explanation: The positive-capacity robot serves the only house while the other robot remains unused.
Hints
- Precompute the best bounded-length route available entirely to the left and entirely to the right of each split. Evaluate both assignments of capacities to the two sides.