Frontend School

Optimal Delivery Sequencing with Time-Sensitive Bonuses

DSA
hard

Optimal Delivery Sequencing with Time-Sensitive Bonuses

Hard
Dynamic Programming
Bit Manipulation
Scheduling

Overview

Uber Eats couriers operate in a dynamic environment, juggling multiple delivery requests to maximize earnings. This problem challenges you to optimize a courier's sequence of deliveries, considering time windows, travel times, and bonus opportunities. The goal is to maximize total earnings by strategically selecting and ordering a subset of available deliveries.

What you need to do / Task

Implement a function maxCourierEarnings that calculates the maximum total earnings a courier can achieve.

  1. Determine which deliveries to accept and in what order.
  2. Adhere to each delivery's readyTime (food pickup) and deliveryDeadline (food dropoff).
  3. Calculate earnings: baseEarnings are always awarded if a delivery is completed. bonusEarnings are awarded only if the delivery is completed by its bonusDeadline.
  4. Account for travel time between deliveries.

Input & output

function maxCourierEarnings(N: number, readyTimes: number[], deliveryDeadlines: number[], baseEarnings: number[], bonusDeadlines: number[], bonusEarnings: number[], travelTimes: number[], interRestaurantTravelTime: number, startTime: number): number

  • N: The total number of available delivery requests.
  • readyTimes: An array of length N, where readyTimes[i] is the earliest time food for delivery i is ready for pickup.
  • deliveryDeadlines: An array of length N, where deliveryDeadlines[i] is the latest time delivery i must be completed.
  • baseEarnings: An array of length N, where baseEarnings[i] is the base payment for delivery i.
  • bonusDeadlines: An array of length N, where bonusDeadlines[i] is the time by which delivery i must be completed to earn the bonus. bonusDeadlines[i] <= deliveryDeadlines[i].
  • bonusEarnings: An array of length N, where bonusEarnings[i] is the additional payment for delivery i if completed by bonusDeadline[i].
  • travelTimes: An array of length N, where travelTimes[i] is the time taken to travel from the restaurant to the customer for delivery i.
  • interRestaurantTravelTime: The fixed time taken to travel between any two consecutive restaurant pickups (i.e., from the dropoff location of the previous delivery to the pickup location of the next delivery). This also applies to the travel time from the courier's startTime location to the first restaurant.
  • startTime: The courier's starting time.

Return: The maximum total earnings the courier can achieve.

Clarifications

  • The courier starts at startTime at an implicit "starting point" (e.g., a central hub). The first delivery's pickup can be reached from this starting point in interRestaurantTravelTime minutes.
  • If the courier arrives at a restaurant before readyTime[i], they must wait until readyTime[i] to pick up the food.
  • All times are non-negative integers.
  • It's possible to complete zero deliveries, in which case the earnings are 0.
  • Assume all deliveries are distinct and independent in terms of locations, except for the interRestaurantTravelTime abstraction.

Examples

1

Example 1

Input:

N = 2, readyTimes = [0, 0], deliveryDeadlines = [100, 100], baseEarnings = [10, 15], bonusDeadlines = [50, 50], bonusEarnings = [5, 10], travelTimes = [20, 30], interRestaurantTravelTime = 10, startTime = 0

Output:

35

Note:

Deliveries: 0: ready=0, deadline=100, base=10, bonus_deadline=50, bonus=5, travel=20 1: ready=0, deadline=100, base=15, bonus_deadline=50, bonus=10, travel=30

Possible sequences and earnings:

  • Only Delivery 0: Arrive restaurant 0 at 10 (0 + 10), pickup at max(10,0)=10, finish at 10+20=30. Bonus applies (30 <= 50). Earnings: 10+5 = 15.
  • Only Delivery 1: Arrive restaurant 1 at 10 (0 + 10), pickup at max(10,0)=10, finish at 10+30=40. Bonus applies (40 <= 50). Earnings: 15+10 = 25.
  • Sequence 0 -> 1: Finish Delivery 0 at 30 (earnings 15). Travel to restaurant 1 (30+10=40). Pickup Delivery 1 at max(40,0)=40, finish at 40+30=70. No bonus for Delivery 1 (70 > 50). Earnings for 1: 15. Total: 15+15 = 30.
  • Sequence 1 -> 0: Finish Delivery 1 at 40 (earnings 25). Travel to restaurant 0 (40+10=50). Pickup Delivery 0 at max(50,0)=50, finish at 50+20=70. No bonus for Delivery 0 (70 > 50). Earnings for 0: 10. Total: 25+10 = 35.

The maximum total earnings is 35.

2

Example 2

Input:

N = 3, readyTimes = [0, 10, 20], deliveryDeadlines = [30, 40, 50], baseEarnings = [10, 20, 30], bonusDeadlines = [25, 35, 45], bonusEarnings = [5, 10, 15], travelTimes = [15, 10, 5], interRestaurantTravelTime = 5, startTime = 0

Output:

90

Note:

Deliveries: 0: ready=0, deadline=30, base=10, bonus_deadline=25, bonus=5, travel=15 1: ready=10, deadline=40, base=20, bonus_deadline=35, bonus=10, travel=10 2: ready=20, deadline=50, base=30, bonus_deadline=45, bonus=15, travel=5

One optimal sequence is 0 -> 1 -> 2:

  • Delivery 0: Arrive restaurant 0 at 5 (0+5), pickup at max(5,0)=5, finish at 5+15=20. Bonus applies (20 <= 25). Earnings: 10+5=15. Current time after dropoff: 20.
  • Delivery 1: Travel to restaurant 1 (20+5=25), pickup at max(25,10)=25, finish at 25+10=35. Bonus applies (35 <= 35). Earnings: 20+10=30. Total: 15+30=45. Current time after dropoff: 35.
  • Delivery 2: Travel to restaurant 2 (35+5=40), pickup at max(40,20)=40, finish at 40+5=45. Bonus applies (45 <= 45). Earnings: 30+15=45. Total: 45+45=90. Current time after dropoff: 45.

Attempting sequence 2 -> 1 -> 0:

  • Delivery 2: Arrive restaurant 2 at 5 (0+5), pickup at max(5,20)=20, finish at 20+5=25. Bonus applies. Earnings: 30+15=45. Current time after dropoff: 25.
  • Delivery 1: Travel to restaurant 1 (25+5=30), pickup at max(30,10)=30, finish at 30+10=40. No bonus (40 > 35). Earnings: 20. Total: 45+20=65. Current time after dropoff: 40.
  • Delivery 0: Travel to restaurant 0 (40+5=45), pickup at max(45,0)=45, finish at 45+15=60. Invalid (60 > deliveryDeadline[0]=30). This path is invalid.

The maximum total earnings is 90.

Constraints

Constraints & assumptions

  • 1 <= N <= 15
  • 0 <= readyTimes[i], deliveryDeadlines[i], bonusDeadlines[i], startTime <= 10^9
  • 0 <= baseEarnings[i], bonusEarnings[i] <= 1000
  • 1 <= travelTimes[i], interRestaurantTravelTime <= 1000
  • bonusDeadlines[i] <= deliveryDeadlines[i] for all i.
  • The courier can only handle one delivery at a time.
  • The courier can choose to skip any delivery.

Out of scope

  • Complex geographical routing (e.g., Dijkstra's on a graph, real-world map data). interRestaurantTravelTime simplifies this.
  • Multi-courier coordination.
  • Dynamic traffic conditions or real-time re-routing.

What interviewers evaluate

  • Ability to model the problem using Dynamic Programming with bitmasking.
  • Correctly defining the DP state and transitions, handling time constraints.
  • Handling edge cases and base conditions accurately.
  • Optimal time and space complexity for the given constraints.

Loading editor...