Maximum earnings from taxi

Array Hash Table Binary Search Dynamic Programming Sorting

46.2% acceptance

Feb 25, 2026

1407

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 integer array rides, where rides[i] = [starti, endi, tipi] denotes the ith passenger requesting a ride from point starti to point endi with a tip of tipi. For each passenger i you pick up, you earn endi - starti + tipi. Return the maximum number of dollars you can earn by picking up the passengers optimally.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_taxi_earnings(_n: i32, rides: Vec<Vec<i32>>) -> i64 {
    let mut rides = rides;
    rides.sort_by_key(|r| r[1]);
    let m = rides.len();
    // dp[i] = max earnings considering first i rides (0-indexed: dp[i+1] for ride i)
    let mut dp = vec![0i64; m + 1];
    for i in 0..m {
      // skip ride i
      dp[i + 1] = dp[i + 1].max(dp[i]);
      // take ride i: find last ride that ends <= rides[i][0]
      let start = rides[i][0];
      let earn = (rides[i][1] - rides[i][0] + rides[i][2]) as i64;
      // binary search for last j where rides[j][1] <= start
      let j = rides[..i].partition_point(|r| r[1] <= start);
      dp[i + 1] = dp[i + 1].max(dp[j] + earn);
    }
    dp[m]
  }
}