Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2008.html

2008. Maximum Earnings From Taxi (Medium)

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

Similar Questions:

Solution 1. DP + Binary Search

Intuition: Almost the same as the classic problem 1235. Maximum Profit in Job Scheduling (Hard).

Algorithm:

  • Sort the array in descending order of start.
  • Store the maximum profit we can get in range [start, Infinity) in a map<int, long long> m.
  • For each A[i], m[start[i]] is either:
    • The maximum profit we’ve seen thus far.
    • Or, profit[i] + (end[i] - start[i]) + P(end[i]), where P is the maximum profit we can get in range [end[i], Infinity). We can get this P value by binary searching the map m – P(end[i]) = m.lower_bound(end[i])->second.
// OJ: https://leetcode.com/problems/maximum-earnings-from-taxi/
// Time: O(MlogM) where `M` is the length of `A`.
// Space: O(M)
class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] > b[0]; }); // Sort the array in descending order of `start`
        map<int, long long> m{ {INT_MAX,0} }; // `dp` value. A mapping from a `start` point to the maximum profit we can get in range `[start, Infinity)`
        long long ans = 0;
        for (auto &r : A) {
            int s = r[0], e = r[1], p = r[2];
            m[s] = max(ans, p + e - s + m.lower_bound(e)->second);
            ans = max(ans, m[s]);
        }
        return ans;
    }
};

Solution 2. DP

// OJ: https://leetcode.com/problems/maximum-earnings-from-taxi/
// Time: O(N + M) where `N` is number of points and `M` is the length of `A`.
// Space: O(N)
class Solution {
public:
    long long maxTaxiEarnings(int n, vector<vector<int>>& A) {
        vector<vector<pair<int, int>>> rideStartAt(n); // group all the rides starting at the same time
        for (auto &ride : A) {
            int s = ride[0], e = ride[1], t = ride[2];
            rideStartAt[s].push_back({ e, e - s + t });  // [end, dollar]
        }
        vector<long long> dp(n + 1);
        for (int i = n - 1; i >= 1; --i) { // Traverse the rides in descending order of start time
            for (auto &[e, d] : rideStartAt[i]) {
                dp[i] = max(dp[i], dp[e] + d);
            }
            dp[i] = max(dp[i], dp[i + 1]);
        }
        return dp[1];
    }
};

All Problems

All Solutions