2008. Maximum Earnings From Taxi

SourceBiweekly Contest 61 Q3DifficultyMediumRating1871

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 0-indexed 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⁵
1 <= rides.length <= 3 * 10⁴
rides[i].length == 3
1 <= start_i < end_i <= n
1 <= tip_i <= 10⁵

Solutions

Solution 1: Memoization Search + Binary Search

Thinking

After sorting rides by start, ride \(i\) only combines with later rides whose start is \(\ge end_i\). Subsets are infeasible for \(m \le 3 \times 10^4\); the state is the best profit from index \(i\).

Skip goes to \(i+1\); take binary-searches the first start \(\ge end_i\) as \(j\) and adds distance, tip, and \(dfs(j)\).

Memoization evaluates each \(i\) once in \(O(m \log m)\).

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\).

Python3JavaC++GoTypeScript

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)

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

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

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

Solution 2: Dynamic Programming + Binary Search

Thinking

Solution 1 is already \(O(m \log m)\), yet recursion and @cache add constants. Sorting by end lets \(f[i]\) be the best profit among the first \(i\) rides, with no aftereffect.

Skip is \(f[i-1]\); take binary-searches the last end \(\le start_i\). Filling \(f\) iteratively removes the call stack.

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:

Python3JavaC++GoTypeScript

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda x: x[1])
        f = [0] * (len(rides) + 1)
        for i, (st, ed, tip) in enumerate(rides, 1):
            j = bisect_left(rides, st + 1, hi=i, key=lambda x: x[1])
            f[i] = max(f[i - 1], f[j] + ed - st + tip)
        return f[-1]

class Solution {
    public long maxTaxiEarnings(int n, int[][] rides) {
        Arrays.sort(rides, (a, b) -> a[1] - b[1]);
        int m = rides.length;
        long[] f = new long[m + 1];
        for (int i = 1; i <= m; ++i) {
            int[] r = rides[i - 1];
            int st = r[0], ed = r[1], tip = r[2];
            int j = search(rides, st + 1, i);
            f[i] = Math.max(f[i - 1], f[j] + ed - st + tip);
        }
        return f[m];
    }

    private int search(int[][] nums, int x, int r) {
        int l = 0;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid][1] >= 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(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
        int m = rides.size();
        vector<long long> f(m + 1);
        for (int i = 1; i <= m; ++i) {
            auto& r = rides[i - 1];
            int st = r[0], ed = r[1], tip = r[2];
            auto it = lower_bound(rides.begin(), rides.begin() + i, st + 1, [](auto& a, int val) { return a[1] < val; });
            int j = distance(rides.begin(), it);
            f[i] = max(f[i - 1], f[j] + ed - st + tip);
        }
        return f.back();
    }
};

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]
}

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

2008. Maximum Earnings From Taxi

Description

Solutions

Solution 1: Memoization Search + Binary Search

Solution 2: Dynamic Programming + Binary Search

Comments