Maximum Earnings From Taxi solution and explanation
9 more videos on this problem
LeetCode 2008. Maximum Earnings From TaxiHappy Coding · 22:45 · 6K views
2008. Maximum Earnings From Taxi (Leetcode Medium)Programming Live with Larry · 14:06 · 3K views
Leetcode 2008 Maximum Earnings From Taxi - Learn How To Solve This Tricky Hard Coding QuestionAlgorithmicIQ · 32:59 · 2K views
Maximum Earnings From TaxiPerfectAlgos · 16:43 · 2K views
Maximum Earnings From Taxi || Leetcode || 2008 || Recursion || Memoization || Binary SearchPerceiver · 17:07 · 1K views
Leetcode 2008. Maximum Earnings From TaxiElite Code · 27:43 · 947 views
【每日一题】LeetCode 2008. Maximum Earnings From Taxi, 9/24/2021Huifeng Guan · 32:43 · 781 views
Leetcode 2008. Maximum Earnings From Taxi (dp max profit)LetsCode · 15:46 · 139 views
LEETCODE 💛🖤 Maximum Earnings From Taxi ( 2008 )CodeClaw( ); · 21:23 · 129 views
2008 Maximum Earnings From Taxi(Python & DP & full walkthru)AlgBreaker · 12:44 · 93 views
The problem
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 <= 1051 <= rides.length <= 3 * 104rides[i].length == 31 <= starti < endi <= n1 <= 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.
from bisect import bisect_right
# Function to compute maximum earnings
def maxTaxiEarnings(n, rides):
# Sort rides based on end point
rides.sort(key=lambda x: x[1])
dp = [0] * (len(rides) + 1)
ends = [ride[1] for ride in rides]
for i in range(len(rides)):
# Binary search for the position where 'start' can be inserted
j = bisect_right(ends, rides[i][0], 0, i)
earning = rides[i][1] - rides[i][0] + rides[i][2]
dp[i + 1] = max(dp[i], dp[j] + earning)
return dp[-1]
# Example usage:
n = 20
rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
print(maxTaxiEarnings(n, rides))import java.util.*;
public class TaxiEarnings {
public static long maxTaxiEarnings(int n, int[][] rides) {
Arrays.sort(rides, Comparator.comparingInt(a -> a[1]));
long[] dp = new long[rides.length + 1];
int[] ends = new int[rides.length];
for (int i = 0; i < rides.length; i++) {
ends[i] = rides[i][1];
}
for (int i = 0; i < rides.length; i++) {
int start = rides[i][0];
int end = rides[i][1];
int tip = rides[i][2];
long earning = end - start + tip;
int j = Arrays.binarySearch(ends, 0, i, start);
if (j < 0) j = -j - 1;
dp[i + 1] = Math.max(dp[i], dp[j] + earning);
}
return dp[rides.length];
}
public static void main(String[] args) {
int[][] rides = {{1,6,1},{3,10,2},{10,12,3},{11,12,2},{12,15,2},{13,18,1}};
int n = 20;
System.out.println(maxTaxiEarnings(n, rides));
}
}#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// Function to return max earnings
typedef long long ll;
int maxTaxiEarnings(int n, vector<vector<int>>& rides) {
// Sort the rides based on end points
sort(rides.begin(), rides.end(), [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
});
int m = rides.size();
vector<ll> dp(m + 1, 0);
for (int i = 0; i < m; ++i) {
int start = rides[i][0], end = rides[i][1], tip = rides[i][2];
ll earn = end - start + tip;
// Binary search to find the position
int j = lower_bound(rides.begin(), rides.begin() + i, vector<int>{0, start, 0}, [](const vector<int>& a, const vector<int>& b) {
return a[1] < b[1];
}) - rides.begin();
dp[i + 1] = max(dp[i], dp[j] + earn);
}
return dp[m];
}
int main() {
vector<vector<int>> rides = {{1, 6, 1}, {3, 10, 2}, {10, 12, 3}, {11, 12, 2}, {12, 15, 2}, {13, 18, 1}};
int n = 20;
cout << maxTaxiEarnings(n, rides);
return 0;
}using System;
using System.Collections.Generic;
public class TaxiEarnings {
public static long MaxTaxiEarnings(int n, int[][] rides) {
Array.Sort(rides, (a, b) => a[1].CompareTo(b[1]));
long[] dp = new long[rides.Length + 1];
List<int> ends = new List<int>();
for (int i = 0; i < rides.Length; i++) {
ends.Add(rides[i][1]);
}
for (int i = 0; i < rides.Length; i++) {
int start = rides[i][0];
int end = rides[i][1];
int tip = rides[i][2];
long earning = end - start + tip;
int j = ends.BinarySearch(0, i, start, null);
if (j < 0) j = ~j;
dp[i + 1] = Math.Max(dp[i], dp[j] + earning);
}
return dp[rides.Length];
}
public static void Main(string[] args) {
int[][] rides = new int[][] {new int[] {1,6,1}, new int[] {3,10,2}, new int[] {10,12,3}, new int[] {11,12,2}, new int[] {12,15,2}, new int[] {13,18,1}};
int n = 20;
Console.WriteLine(MaxTaxiEarnings(n, rides));
}
}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.
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.
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.
import heapq
# Function to compute maximum earnings
def maxTaxiEarnings(n, rides):
rides.sort()
max_earnings_heap = [] # max heap for earnings
max_earnings_end = 0
for start, end, tip in rides:
while max_earnings_heap and max_earnings_heap[0][0] <= start:
max_earnings_end = max(max_earnings_end, heapq.heappop(max_earnings_heap)[1])
current_profit = end - start + tip
heapq.heappush(max_earnings_heap, (end, max_earnings_end + current_profit))
# Resolve the max among the remaining potential rides in the heap
while max_earnings_heap:
max_earnings_end = max(max_earnings_end, heapq.heappop(max_earnings_heap)[1])
return max_earnings_end
# Example usage:
n = 20
rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
print(maxTaxiEarnings(n, rides))function maxTaxiEarnings(n, rides) {
rides.sort((a, b) => a[0] - b[0]);
const pq = [];
let maxEarningsEnd = 0;
for (const [start, end, tip] of rides) {
while (pq.length && pq[0][0] <= start) {
maxEarningsEnd = Math.max(maxEarningsEnd, pq.shift()[1]);
}
// Add the current ride to the potential earning options
const currentEarning = end - start + tip;
pq.push([end, maxEarningsEnd + currentEarning]);
pq.sort((a, b) => a[0] - b[0]); // Ensure by end order
}
while (pq.length) {
maxEarningsEnd = Math.max(maxEarningsEnd, pq.shift()[1]);
}
return maxEarningsEnd;
}
// Example usage
const n = 20;
const rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]];
console.log(maxTaxiEarnings(n, rides));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.
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.
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$.
function maxTaxiEarnings(n: number, rides: number[][]): number {
rides.sort((a, b) => a[0] - b[0]);
const m = rides.length;
const f: number[] = Array(m).fill(-1);
const search = (x: number, l: number): number => {
let r = m;
while (l < r) {
const mid = (l + r) >> 1;
if (rides[mid][0] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const dfs = (i: number): number => {
if (i >= m) {
return 0;
}
if (f[i] === -1) {
const [st, ed, tip] = rides[i];
const j = search(ed, i + 1);
f[i] = Math.max(dfs(i + 1), dfs(j) + ed - st + tip);
}
return f[i];
};
return dfs(0);
}func maxTaxiEarnings(n int, rides [][]int) int64 {
sort.Slice(rides, func(i, j int) bool { return rides[i][0] < rides[j][0] })
m := len(rides)
f := make([]int64, m)
var dfs func(int) int64
dfs = func(i int) int64 {
if i >= m {
return 0
}
if f[i] == 0 {
st, ed, tip := rides[i][0], rides[i][1], rides[i][2]
j := sort.Search(m, func(j int) bool { return rides[j][0] >= ed })
f[i] = max(dfs(i+1), int64(ed-st+tip)+dfs(j))
}
return f[i]
}
return dfs(0)
}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:
function maxTaxiEarnings(n: number, rides: number[][]): number {
rides.sort((a, b) => a[1] - b[1]);
const m = rides.length;
const f: number[] = Array(m + 1).fill(0);
const search = (x: number, r: number): number => {
let l = 0;
while (l < r) {
const mid = (l + r) >> 1;
if (rides[mid][1] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 1; i <= m; ++i) {
const [st, ed, tip] = rides[i - 1];
const j = search(st + 1, i);
f[i] = Math.max(f[i - 1], f[j] + ed - st + tip);
}
return f[m];
}func maxTaxiEarnings(n int, rides [][]int) int64 {
sort.Slice(rides, func(i, j int) bool { return rides[i][1] < rides[j][1] })
m := len(rides)
f := make([]int64, m+1)
for i := 1; i <= m; i++ {
r := rides[i-1]
st, ed, tip := r[0], r[1], r[2]
j := sort.Search(m, func(j int) bool { return rides[j][1] >= st+1 })
f[i] = max(f[i-1], f[j]+int64(ed-st+tip))
}
return f[m]
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
| Greedy + Dynamic Programming Optimization Strategy | Time Complexity: O(m log m), as sort and heap operations predominantly dictate performance times. |
| Memoization Search + Binary Search | – |
| Dynamic Programming + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Quadratic Dynamic Programming | O(m²) | O(m) | Conceptual baseline to understand weighted interval scheduling |
| DP with Binary Search | O(m log m) | O(m) | General optimal solution when rides are treated as intervals |
| Greedy Sweep + DP by Position | O(n + m log m) | O(n) | Efficient when iterating along road positions and grouping rides by start |
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.