Optimal Delivery Sequencing with Time-Sensitive Bonuses
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.
Implement a function maxCourierEarnings that calculates the maximum total earnings a courier can achieve.
readyTime (food pickup) and deliveryDeadline (food dropoff).baseEarnings are always awarded if a delivery is completed. bonusEarnings are awarded only if the delivery is completed by its bonusDeadline.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.
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.readyTime[i], they must wait until readyTime[i] to pick up the food.interRestaurantTravelTime abstraction.Examples
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:
The maximum total earnings is 35.
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:
Attempting sequence 2 -> 1 -> 0:
The maximum total earnings is 90.
Constraints
1 <= N <= 150 <= readyTimes[i], deliveryDeadlines[i], bonusDeadlines[i], startTime <= 10^90 <= baseEarnings[i], bonusEarnings[i] <= 10001 <= travelTimes[i], interRestaurantTravelTime <= 1000bonusDeadlines[i] <= deliveryDeadlines[i] for all i.interRestaurantTravelTime simplifies this.Loading editor...