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
Solution: DP
dp[i] := max earnings we can get at position i and the taxi is empty.
dp[i] = max(dp[i – 1], dp[s] + gain) where e = i, gain = e – s + tips
For each i, we check all the rides that end at i and find the best one (which may have different starting points), otherwise the earning will be the same as previous position (i – 1).
answer = dp[n]
Time complexity: O(m + n)
Space complexity: O(m + n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua class Solution { public: long long maxTaxiEarnings(int n, vector<vector<int>>& rides) { vector<long long> dp(n + 1); vector<vector<pair<int, int>>> m(n + 1); for (const auto& r : rides) m[r[1]].emplace_back(r[0], r[1] - r[0] + r[2]); for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1]; for (const auto [s, g] : m[i]) dp[i] = max(dp[i], dp[s] + g); } return dp[n]; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment