Skip to main content
Talentd

Maximum Earnings From Taxi - Solution & Explanation

MediumArrayHash TableBinary SearchDynamic Programming25 min readAsked at: Wells Fargo, Meta, Oracle +5
Practice this problem

Problem Statement

There are n points on a road you are driving your taxi on. The n points on the road are labeled from 1 to n in the direction you are going, and you want to drive from point 1 to point n to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a 0-indexed 2D integer array rides, where rides[i] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi who is willing to give a tipi dollar tip.

For each passenger i you pick up, you earn endi - starti + tipi dollars. You may only drive at most one passenger at a time.

Given n and rides, return the maximum number of dollars you can earn by picking up the passengers optimally.

Note: You may drop off a passenger and pick up a different passenger at the same point.

 

Example 1:

Input: n = 5, rides = [[2,5,4],[1,5,1]]
Output: 7
Explanation: We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

Example 2:

Input: n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output: 20
Explanation: We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

 

Constraints:

  • 1 <= n <= 105
  • 1 <= rides.length <= 3 * 104
  • rides[i].length == 3
  • 1 <= starti < endi <= n
  • 1 <= tipi <= 105

Approach Overview

Problem Overview: You drive a taxi on a road with locations from 1 to n. Each ride has a start point, end point, and tip. When you accept a ride you must complete it before starting another. The task is to select a set of non‑overlapping rides that maximizes total earnings (end - start + tip).

Approach 1: Quadratic Dynamic Programming (O(m²) time, O(m) space)

Sort all rides by their end position using sorting. Define dp[i] as the maximum profit considering rides up to index i. For each ride i, compute its earnings and check every previous ride j. If rides[j].end <= rides[i].start, the two rides are compatible and you can combine their profits. Update dp[i] = max(dp[i], dp[j] + profit_i). This approach clearly models the weighted interval scheduling idea but becomes slow because every ride scans all previous rides.

Approach 2: Dynamic Programming with Binary Search (O(m log m) time, O(m) space)

After sorting rides by end location, maintain a DP array where dp[i] stores the maximum earnings using the first i rides. For each ride, compute its profit and use binary search to find the last ride whose end point is <= start. This gives the best compatible ride in O(log m). The transition becomes dp[i] = max(dp[i-1], dp[prev] + profit). The key insight: because rides are sorted by end time, compatible rides form a prefix, so binary search replaces the quadratic scan.

Approach 3: Greedy + Dynamic Programming Optimization (O(n + m log m) time, O(n) space)

Instead of indexing DP by rides, index it by road position. Create a map from start position to rides beginning there using an array or adjacency list. Iterate positions from 1 to n and carry forward the best earnings so far: dp[i] = max(dp[i], dp[i-1]). For every ride starting at i, update dp[end] = max(dp[end], dp[i] + end - start + tip). This acts like a greedy sweep along the road while still relying on dynamic programming. It avoids searching previous rides and works well when n is manageable.

Recommended for interviews: Dynamic Programming with Binary Search is the expected solution. It shows you recognize the weighted interval scheduling pattern and know how to optimize the compatibility check with binary search. Starting with the quadratic DP demonstrates understanding of the state transition, but the optimized O(m log m) approach shows strong algorithmic reasoning.

Approach 1: Dynamic Programming with Binary Search

In this approach, we utilize dynamic programming along with binary search to maximize earnings. The idea is to process rides in order of their end points. For each ride, we use binary search to efficiently find the maximum profit we can accumulate until the start point of the current ride. This helps in deciding if we should pick up the current ride to maximize profits.

We maintain a 'dp' array where 'dp[i]' stores the maximum profit that can be earned by considering rides up to point 'i'. We iterate through each ride, check if taking this ride improves the overall profit compared to not taking it, using the `dp` value at the ride's start point. We use binary search to quickly find the previous rides that end before the current ride starts.

This solution leverages dynamic programming to calculate the maximum fundable earnings route. We transform the problem into a decision-making process of whether to take the next ride by adding to previous maximum earnings at the start point or not. Sorting rides based on their end point enables efficient use of binary search to determine past contributing segments.

Code

PythonC++JavaC#

Python

C++

Java

C#

Complexity

Time Complexity: O(m log m) where m is the number of rides. Sorting takes O(m log m) and for each ride, binary search might take O(m log m) in the worst case.
Space Complexity: O(m) for the dp array.

Try this approach in the editor →

Approach 2: Greedy + Dynamic Programming Optimization Strategy

This approach fuses a priority queue (or heap) with dynamic programming to select optimal rides greedily based on profit potential. We utilize a max heap to track ongoing ride profits and dynamically update potential maximums as the rides process. The goal is to rapidly determine and add the best potential future profits.

In this strategy, rides are evaluated over possible earnings, allowing the priority mechanism to determine profitable pickups optimally faster.

This Python solution embraces a heuristic approach combining greedy ride picking strategies via a priority queue, and updating potential revenues efficiently. Sorting rides and managing a dynamic records heap permits optimal profit accumulation for solving the specified task efficiently.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(m log m), as sort and heap operations predominantly dictate performance times.
Space Complexity: O(m), considering the heap and storage elements.

Try this approach in the editor →

Approach 3: Memoization Search + Binary Search

First, we sort rides in ascending order by start. Then we design a function dfs(i), which represents the maximum tip that can be obtained from accepting orders starting from the i-th passenger. The answer is dfs(0).

The calculation process of the function dfs(i) is as follows:

For the i-th passenger, we can choose to accept or not to accept the order. If we don't accept the order, the maximum tip that can be obtained is dfs(i + 1). If we accept the order, we can use binary search to find the first passenger encountered after the drop-off point of the i-th passenger, denoted as j. The maximum tip that can be obtained is dfs(j) + end_i - start_i + tip_i. Take the larger of the two. That is:

$ dfs(i) = max(dfs(i + 1), dfs(j) + end_i - start_i + tip_i)

Where j is the smallest index that satisfies start_j \ge end_i, which can be obtained by binary search.

In this process, we can use memoization search to save the answer of each state to avoid repeated calculations.

The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the length of rides$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Approach 4: Dynamic Programming + Binary Search

We can change the memoization search in Solution 1 to dynamic programming.

First, sort rides, this time we sort by end in ascending order. Then define f[i], which represents the maximum tip that can be obtained from the first i passengers. Initially, f[0] = 0, and the answer is f[m].

For the i-th passenger, we can choose to accept or not to accept the order. If we don't accept the order, the maximum tip that can be obtained is f[i-1]. If we accept the order, we can use binary search to find the last passenger whose drop-off point is not greater than start_i before the i-th passenger gets on the car, denoted as j. The maximum tip that can be obtained is f[j] + end_i - start_i + tip_i. Take the larger of the two. That is:

$ f[i] = max(f[i - 1], f[j] + end_i - start_i + tip_i)

Where j is the largest index that satisfies end_j \le start_i, which can be obtained by binary search.

The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the length of rides$.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Binary Search

Time Complexity: O(m log m) where m is the number of rides. Sorting takes O(m log m) and for each ride, binary search might take O(m log m) in the worst case.
Space Complexity: O(m) for the dp array.

Greedy + Dynamic Programming Optimization Strategy

Time Complexity: O(m log m), as sort and heap operations predominantly dictate performance times.
Space Complexity: O(m), considering the heap and storage elements.

Memoization Search + Binary Search—
Dynamic Programming + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Quadratic Dynamic ProgrammingO(m²)O(m)Conceptual baseline to understand weighted interval scheduling
DP with Binary SearchO(m log m)O(m)General optimal solution when rides are treated as intervals
Greedy Sweep + DP by PositionO(n + m log m)O(n)Efficient when iterating along road positions and grouping rides by start

Video Solution

LeetCode 2008. Maximum Earnings From Taxi • Happy Coding • 6,286 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Earnings From Taxi easy or hard?
Maximum Earnings From Taxi is rated Medium difficulty. The challenge comes from recognizing it as a weighted interval scheduling problem and applying dynamic programming with binary search to optimize the ride compatibility check.
How to solve Maximum Earnings From Taxi in O(n)?
An optimized sweep approach processes road positions from 1 to n while storing rides grouped by their start point. At each position you propagate the best profit forward and update profits for rides that start there. This dynamic programming sweep runs in O(n + m) after preprocessing.
Maximum Earnings From Taxi Python or Java solution?
Both Python and Java implementations typically sort rides by end time and use dynamic programming with binary search. The DP array tracks the best earnings so far, and binary search quickly finds the previous compatible ride to combine profits.
What is the best approach for Maximum Earnings From Taxi?
Dynamic Programming with Binary Search is the most common optimal approach. After sorting rides by end position, binary search finds the last compatible ride for each interval. The DP transition combines the previous maximum earnings with the current ride profit, giving O(m log m) time complexity.
Is Maximum Earnings From Taxi asked at Google/Amazon/Meta?
This problem follows the classic weighted interval scheduling pattern, a common interview topic at companies like Google, Amazon, and Meta. Variants appear in scheduling, job selection, and profit maximization questions involving non-overlapping intervals.
What data structure is used in Maximum Earnings From Taxi?
Key structures include arrays for storing rides, sorting utilities for ordering intervals by end time, and dynamic programming arrays for tracking maximum profit. The optimized approach also uses binary search on sorted ride endpoints.
What is the time complexity of Maximum Earnings From Taxi?
The optimal solution runs in O(m log m) time where m is the number of rides. Sorting the rides costs O(m log m), and each DP step performs a binary search to find the last compatible ride. Space complexity is O(m) for the DP array.

Ready to solve this problem?

Practice Maximum Earnings From Taxi with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Events That Can Be Attended

Next

Maximum Number of Events That Can Be Attended II