Quick Overview

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.

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

  1. 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.

Loading coding console...