Welcome to Subscribe On Youtube
2008. Maximum Earnings From Taxi
Description
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 0indexed 2D integer array rides
, where rides[i] = [start_{i}, end_{i}, tip_{i}]
denotes the i^{th}
passenger requesting a ride from point start_{i}
to point end_{i}
who is willing to give a tip_{i}
dollar tip.
For each passenger i
you pick up, you earn end_{i}  start_{i} + tip_{i}
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 <= 10^{5}
1 <= rides.length <= 3 * 10^{4}
rides[i].length == 3
1 <= start_{i} < end_{i} <= n
1 <= tip_{i} <= 10^{5}
Solutions
Solution 1: 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 dropoff 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$.
Solution 2: 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[i1]$. If we accept the order, we can use binary search to find the last passenger whose dropoff 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$.

class Solution { private int m; private int[][] rides; private Long[] f; public long maxTaxiEarnings(int n, int[][] rides) { Arrays.sort(rides, (a, b) > a[0]  b[0]); m = rides.length; f = new Long[m]; this.rides = rides; return dfs(0); } private long dfs(int i) { if (i >= m) { return 0; } if (f[i] != null) { return f[i]; } int[] r = rides[i]; int st = r[0], ed = r[1], tip = r[2]; int j = search(ed, i + 1); return f[i] = Math.max(dfs(i + 1), dfs(j) + ed  st + tip); } private int search(int x, int l) { int r = m; while (l < r) { int mid = (l + r) >> 1; if (rides[mid][0] >= x) { r = mid; } else { l = mid + 1; } } return l; } }

class Solution { public: long long maxTaxiEarnings(int n, vector<vector<int>>& rides) { sort(rides.begin(), rides.end()); int m = rides.size(); long long f[m]; memset(f, 1, sizeof(f)); function<long long(int)> dfs = [&](int i) > long long { if (i >= m) { return 0; } if (f[i] != 1) { return f[i]; } auto& r = rides[i]; int st = r[0], ed = r[1], tip = r[2]; int j = lower_bound(rides.begin() + i + 1, rides.end(), ed, [](auto& a, int val) { return a[0] < val; })  rides.begin(); return f[i] = max(dfs(i + 1), dfs(j) + ed  st + tip); }; return dfs(0); } };

class Solution: def maxTaxiEarnings(self, n: int, rides: List[List[int]]) > int: @cache def dfs(i: int) > int: if i >= len(rides): return 0 st, ed, tip = rides[i] j = bisect_left(rides, ed, lo=i + 1, key=lambda x: x[0]) return max(dfs(i + 1), dfs(j) + ed  st + tip) rides.sort() 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(edst+tip)+dfs(j)) } return f[i] } return dfs(0) }

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); }