Maximize Driver Tips
Uber Eats drivers strive to maximize their earnings by strategically choosing which orders to fulfill. Given a list of potential orders, each with a specific pickup time, delivery time, and an associated tip amount, a driver wants to select a subset of orders such that no two selected orders conflict (i.e., a driver can only handle one order at a time), and the total tip amount is maximized. This problem focuses on optimizing a single driver's route to maximize their earnings.
Your task is to implement a function maxDriverTips that takes an array of Order objects and returns the maximum total tip amount a driver can earn by fulfilling a non-overlapping subset of these orders.
Input:
orders: An array of Order objects. Each Order object has the following properties:
pickupTime: A number representing the start time of the order.deliveryTime: A number representing the end time of the order.tipAmount: A number representing the tip earned for completing this order.Return: A single number representing the maximum total tip amount the driver can earn.
Function Signature:
interface Order {
pickupTime: number;
deliveryTime: number;
tipAmount: number;
}
function maxDriverTips(orders: Order[]): number {
// your code here
}
A and B conflict if their time intervals [A.pickupTime, A.deliveryTime] and [B.pickupTime, B.deliveryTime] strictly overlap. An order starts exactly at pickupTime and finishes exactly at deliveryTime. A driver can immediately start a new order at deliveryTime of a previous one. For example, an order ending at 5 and another starting at 5 do not conflict ([1, 5] and [5, 10] are compatible).orders array is empty, the driver earns 0 tips.tipAmount values will be non-negative.Examples
Example 1
Input:
orders = [{"pickupTime": 1, "deliveryTime": 3, "tipAmount": 20}, {"pickupTime": 2, "deliveryTime": 5, "tipAmount": 30}, {"pickupTime": 4, "deliveryTime": 6, "tipAmount": 25}]
Output:
45
Note:
Sorted orders:
{"pickupTime": 1, "deliveryTime": 3, "tipAmount": 20}{"pickupTime": 2, "deliveryTime": 5, "tipAmount": 30}{"pickupTime": 4, "deliveryTime": 6, "tipAmount": 25}If we pick order 1 (tip 20), the next available time is 3. We can then pick order 3 (starts at 4), total tip = 20 + 25 = 45. If we pick order 2 (tip 30), no other compatible orders can be picked (order 1 ends at 3, order 3 starts at 4, but order 2 ends at 5, so 3 and 4 are not compatible with order 2). Total tip = 30. The maximum is 45.
Example 2
Input:
orders = [{"pickupTime": 1, "deliveryTime": 2, "tipAmount": 10}, {"pickupTime": 2, "deliveryTime": 3, "tipAmount": 15}, {"pickupTime": 3, "deliveryTime": 4, "tipAmount": 5}]
Output:
30
Note:
All orders can be picked sequentially as their intervals do not strictly overlap: Order 1: [1, 2], tip 10. Order 2: [2, 3], tip 15. Order 3: [3, 4], tip 5. Total tip = 10 + 15 + 5 = 30.
Example 3
Input:
orders = [{"pickupTime": 10, "deliveryTime": 20, "tipAmount": 100}, {"pickupTime": 15, "deliveryTime": 25, "tipAmount": 50}]
Output:
100
Note:
Only one order can be picked due to overlap. Picking the first order yields 100. Picking the second yields 50. The maximum is 100.
Constraints
0 <= orders.length <= 10^50 <= pickupTime < deliveryTime <= 10^9 for any given order.0 <= tipAmount <= 10^4pickupTime and deliveryTime values are integers.Loading editor...