Frontend School

Maximize Driver Tips

DSA
medium

Maximize Driver Tips

Medium
Dynamic Programming
Sorting
Binary Search

Overview

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.

What you need to do / Task

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 & Output

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
}

Clarifications

  • Order Overlap: Two orders 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).
  • Empty Input: If the orders array is empty, the driver earns 0 tips.
  • Non-negative Tips: All tipAmount values will be non-negative.

Examples

1

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:

  1. {"pickupTime": 1, "deliveryTime": 3, "tipAmount": 20}
  2. {"pickupTime": 2, "deliveryTime": 5, "tipAmount": 30}
  3. {"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.

2

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.

3

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

Constraints & assumptions

  • 0 <= orders.length <= 10^5
  • 0 <= pickupTime < deliveryTime <= 10^9 for any given order.
  • 0 <= tipAmount <= 10^4
  • All pickupTime and deliveryTime values are integers.
  • The driver can only fulfill one order at a time.
  • Times are absolute (e.g., Unix timestamps or minutes from midnight).

Out of scope

  • Real-time order changes or dynamic pricing.
  • Geographical constraints or travel time between orders.
  • Optimizing for multiple drivers or vehicle types.
  • Considering driver fatigue or breaks.

What interviewers evaluate

  • Correctness and Robustness: The solution must correctly calculate the maximum tips for all valid inputs, including edge cases.
  • Efficiency: The solution should be performant in terms of both time and space complexity, scaling well with a large number of orders.
  • Algorithmic Approach: Demonstrates a clear understanding of how to apply sorting, searching, and dynamic programming principles to solve the problem efficiently.
  • Code Quality: Writes clean, readable, and well-structured code with appropriate data structures and variable names.

Loading editor...