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
class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
@cache
def dfs(i):
if i >= len(rides):
return 0
s, e, t = rides[i]
j = bisect_left(rides, e, lo=i + 1, key=lambda x: x[0])
return max(dfs(i + 1), dfs(j) + e - s + t)
rides.sort()
return dfs(0)class Solution:
def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
rides.sort(key=lambda x: x[1])
m = len(rides)
dp = [0] * (m + 1)
for i, (s, e, t) in enumerate(rides):
j = bisect_right(rides, s, hi=i, key=lambda x: x[1])
dp[i + 1] = max(dp[i], dp[j] + e - s + t)
return dp[m]class Solution {
private int[][] rides;
private long[] f;
private int m;
public long maxTaxiEarnings(int n, int[][] rides) {
m = rides.length;
f = new long[m];
Arrays.sort(rides, (a, b) -> a[0] - b[0]);
this.rides = rides;
return dfs(0);
}
private long dfs(int i) {
if (i >= m) {
return 0;
}
if (f[i] != 0) {
return f[i];
}
int s = rides[i][0], e = rides[i][1], t = rides[i][2];
int j = search(rides, e, i + 1);
long ans = Math.max(dfs(i + 1), dfs(j) + e - s + t);
f[i] = ans;
return ans;
}
private int search(int[][] rides, int x, int i) {
int left = i, right = m;
while (left < right) {
int mid = (left + right) >> 1;
if (rides[mid][0] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}class Solution {
public long maxTaxiEarnings(int n, int[][] rides) {
Arrays.sort(rides, (a, b) -> a[1] - b[1]);
int m = rides.length;
long[] dp = new long[m + 1];
for (int i = 0; i < m; ++i) {
int s = rides[i][0], e = rides[i][1], t = rides[i][2];
int j = search(rides, s, i);
dp[i + 1] = Math.max(dp[i], dp[j] + e - s + t);
}
return dp[m];
}
private int search(int[][] rides, int x, int n) {
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (rides[mid][1] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}using ll = long long;
class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
sort(rides.begin(), rides.end());
int m = rides.size();
vector<ll> f(m);
vector<int> x(3);
function<ll(int)> dfs = [&](int i) -> ll {
if (i >= m) return 0;
if (f[i]) return f[i];
int s = rides[i][0], e = rides[i][1], t = rides[i][2];
x[0] = e;
int j = lower_bound(rides.begin() + i + 1, rides.end(), x, [&](auto& l, auto& r) -> bool { return l[0] < r[0];}) - rides.begin();
ll ans = max(dfs(i + 1), dfs(j) + e - s + t);
f[i] = ans;
return ans;
};
return dfs(0);
}
};using ll = long long;
class Solution {
public:
long long maxTaxiEarnings(int n, vector<vector<int>>& rides) {
sort(rides.begin(), rides.end(), [&](auto& l, auto& r) -> bool { return l[1] < r[1]; });
int m = rides.size();
vector<ll> dp(m + 1);
vector<int> x(3);
for (int i = 0; i < m; ++i) {
int s = rides[i][0], e = rides[i][1], t = rides[i][2];
x[1] = s;
int j = upper_bound(rides.begin(), rides.begin() + i, x, [&](auto& l, auto& r) -> bool { return l[1] < r[1]; }) - rides.begin();
dp[i + 1] = max(dp[i], dp[j] + e - s + t);
}
return dp[m];
}
};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 {
return f[i]
}
s, e, t := rides[i][0], rides[i][1], rides[i][2]
j := sort.Search(m, func(k int) bool { return rides[k][0] >= e })
ans := max(dfs(i+1), dfs(j)+int64(e-s+t))
f[i] = ans
return ans
}
return dfs(0)
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}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)
dp := make([]int64, m+1)
for i, ride := range rides {
s, e, t := ride[0], ride[1], ride[2]
j := sort.Search(m, func(k int) bool { return rides[k][1] > s })
dp[i+1] = max(dp[i], dp[j]+int64(e-s+t))
}
return dp[m]
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}