Katkat
Back

Maximize Revenue With Two Contiguous Delivery Routes

NuroSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests dynamic programming and prefix-max techniques to find the maximum revenue of two non-overlapping subarrays with given length constraints.

Problem Statement

You are managing a fleet of two delivery robots, Robot A and Robot B. You are given an array revenue where revenue[i] represents the profit from a delivery at location i.

Robot A must complete a contiguous route of exactly length L1, and Robot B must complete a contiguous route of exactly length L2. The two routes must not overlap. Your goal is to maximize the combined revenue of both routes.

Function Signature

def max_delivery_revenue(revenue: List[int], L1: int, L2: int) -> int:

Constraints

  • 2 <= len(revenue) <= 10^5
  • 1 <= L1, L2
  • L1 + L2 <= len(revenue)
  • 0 <= revenue[i] <= 10^9

Example 1

Input: revenue = [1, 2, 5, 2, 1], L1 = 1, L2 = 2 Output: 9 Explanation: Robot A takes index 2 (revenue 5), Robot B takes indices 3-4 (revenue 2+1=3) or Robot B takes 0-1 (revenue 1+2=3). Total is 5 + 3 = 8. Wait, if A takes index 2 (5) and B takes 0-1 (3), that's 8. If A takes 1 (2) and B takes 2-3 (7), total is 9.

Edge Cases

  • L1 + L2 equals the length of the array.
  • The array contains very large integers, potentially causing overflow in languages with fixed-width integers.
  • All revenues are equal.

Hints

Hint 1

Use a sliding window or prefix sums to calculate the revenue of any contiguous subarray of length L in O(1) time.

Hint 2

Precompute an array where `max_left[i]` stores the maximum revenue of a subarray of length `L1` ending at or before index `i`.

Hint 3

Iterate through all possible positions for the second robot and use the precomputed `max_left` values to find the best non-overlapping position for the first robot.

Follow-up questions

  • How would you modify your solution if the routes must be separated by at least one delivery location?
  • What changes are required if the robots can pick any length between 1 and L, inclusive?
  • How would you approach this problem if you needed to coordinate three robots instead of two?