LeetCode 2008 - Maximum Earnings From Taxi

The problem describes a taxi traveling along a one directional road from point 1 to point n. Along the way, passengers request rides. Each ride is represented as [start, end, tip], meaning the passenger wants to travel from start to end and will additionally pay a tip.

leetcodemediumarrayhash-tablebinary-searchdynamic-programmingsorting

LeetCode Problem 2008

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem describes a taxi traveling along a one directional road from point 1 to point n. Along the way, passengers request rides. Each ride is represented as [start, end, tip], meaning the passenger wants to travel from start to end and will additionally pay a tip.

If we accept a ride, the total money earned from that passenger is:

$$(end - start) + tip$$

The taxi can only carry one passenger at a time, which means we cannot take overlapping rides. However, we can immediately start another ride at the exact point where the previous ride ends.

The goal is to determine the maximum total earnings possible by choosing an optimal subset of non-overlapping rides.

The constraints are important:

  • n can be as large as 10^5
  • rides.length can be as large as 3 * 10^4

A brute force search over all subsets of rides would be impossible because the number of subsets grows exponentially.

The rides are also not guaranteed to be sorted, so we must process them efficiently.

An important observation is that this problem is essentially a weighted interval scheduling problem:

  • Each ride is an interval [start, end]
  • Each ride has a profit end - start + tip
  • We want the maximum profit subset of non-overlapping intervals

Important edge cases include:

  • Multiple rides ending at the same location
  • Multiple rides starting at the same location
  • Rides that chain perfectly together
  • Cases where taking one large ride is worse than taking several smaller rides
  • Cases where no rides overlap at all
  • Cases where nearly every ride overlaps

The problem guarantees:

  • start < end
  • All points lie between 1 and n
  • Tips are positive integers

These guarantees simplify implementation because we never need to handle invalid intervals.

Approaches

Brute Force Approach

A straightforward solution is to try every possible subset of rides.

For each subset, we would:

  1. Check whether the rides overlap
  2. Compute the total earnings if they do not overlap
  3. Keep track of the maximum valid earnings

This works because it explores every possible combination, so the optimal solution must eventually be found.

However, this approach is far too slow. If there are m rides, there are 2^m subsets. Since m can be up to 3 * 10^4, exponential time is completely infeasible.

Even adding pruning or memoization would still struggle unless we exploit the interval structure more intelligently.

Key Insight

The key observation is that rides only conflict based on their intervals.

If we sort rides by ending position, then for every ride we can determine:

  • The profit earned by taking this ride
  • The best profit achievable before this ride starts

This naturally leads to dynamic programming.

For each ride:

$$dp[i] = \max( \text{skip current ride}, \text{take current ride} )$$

To efficiently find the best previous compatible ride, we use binary search.

This transforms the problem into a classic weighted interval scheduling problem with:

  • Sorting
  • Dynamic programming
  • Binary search

This gives an efficient solution that fits comfortably within the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^m) O(m) Tries every subset of rides
Optimal O(m log m) O(m) Dynamic programming with binary search

Here, m = len(rides).

Algorithm Walkthrough

  1. Sort all rides by their ending position.

Sorting by end time allows us to process rides in chronological order. When considering a ride, all previously processed rides end no later than the current ride. 2. Compute the profit of each ride.

For a ride [start, end, tip], the earnings are:

$$profit = (end - start) + tip$$ 3. Create a list of sorted end positions.

We store all ride ending points separately because we will use binary search to quickly find the latest ride that finishes before the current ride starts. 4. Define the DP state.

Let dp[i] represent the maximum earnings achievable using the first i rides in sorted order.

This means:

  • dp[0] = 0
  • dp[i] stores the best possible profit considering rides up to index i - 1
  1. Process rides one by one.

For each ride:

  • Use binary search to find the rightmost ride whose end point is less than or equal to the current ride's start point
  • This gives the latest compatible ride
  1. Compute two choices.

For the current ride:

  • Skip it:

$$dp[i] = dp[i-1]$$

  • Take it:

$$dp[compatible] + currentProfit$$ 7. Store the maximum.

The best answer for dp[i] is the larger of the two choices. 8. Return the final result.

The answer is stored in the last DP entry.

Why it works

The algorithm works because every ride decision is independent once we know the latest compatible previous ride.

At each step, the optimal solution must either:

  • Exclude the current ride
  • Include the current ride and combine it with the best compatible solution before it

Since the DP table always stores optimal answers for smaller prefixes, combining them preserves optimality. Binary search ensures we efficiently locate compatible rides.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort(key=lambda ride: ride[1])

        ends = [ride[1] for ride in rides]

        m = len(rides)
        dp = [0] * (m + 1)

        for i in range(1, m + 1):
            start, end, tip = rides[i - 1]

            profit = end - start + tip

            compatible_index = bisect_right(ends, start, hi=i - 1)

            take = dp[compatible_index] + profit
            skip = dp[i - 1]

            dp[i] = max(skip, take)

        return dp[m]

The implementation begins by sorting rides according to their ending positions. This ordering is essential because the DP recurrence depends on previously completed rides.

The ends array stores all ride end positions separately. This enables binary search using bisect_right.

The DP array has size m + 1, where m is the number of rides. Using one based indexing for DP simplifies transitions because dp[i] naturally represents the answer using the first i rides.

For each ride:

  • We compute its profit
  • We binary search for the last compatible ride
  • We compute the profit if we take the ride
  • We compare it with the profit if we skip the ride

The maximum of these two choices becomes the DP value for the current position.

Finally, dp[m] contains the optimal total earnings.

Go Solution

package main

import (
	"sort"
)

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)

	ends := make([]int, m)
	for i := 0; i < m; i++ {
		ends[i] = rides[i][1]
	}

	dp := make([]int64, m+1)

	for i := 1; i <= m; i++ {
		start := rides[i-1][0]
		end := rides[i-1][1]
		tip := rides[i-1][2]

		profit := int64(end - start + tip)

		compatibleIndex := sort.Search(i-1, func(j int) bool {
			return ends[j] > start
		})

		take := dp[compatibleIndex] + profit
		skip := dp[i-1]

		if take > skip {
			dp[i] = take
		} else {
			dp[i] = skip
		}
	}

	return dp[m]
}

The Go implementation follows the same logic as the Python solution.

The main difference is that Go requires explicit handling of integer sizes. Since total earnings can become large, the DP array uses int64.

Go does not have a built in bisect utility like Python, so sort.Search is used to implement binary search.

Slices are used instead of Python lists, but the overall DP structure remains identical.

Worked Examples

Example 1

Input:

n = 5
rides = [[2,5,4],[1,5,1]]

Step 1: Sort by end

Ride Profit
[2,5,4] 7
[1,5,1] 5

Both rides end at 5.

DP Processing

i Current Ride Compatible Index Take Skip dp[i]
1 [2,5,4] 0 7 0 7
2 [1,5,1] 0 5 7 7

Final answer:

7

Example 2

Input:

n = 20
rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]

Step 1: Sort rides

Ride Profit
[1,6,1] 6
[3,10,2] 9
[10,12,3] 5
[11,12,2] 3
[12,15,2] 5
[13,18,1] 6

DP Processing

i Ride Compatible Index Take Skip dp[i]
1 [1,6,1] 0 6 0 6
2 [3,10,2] 0 9 6 9
3 [10,12,3] 2 14 9 14
4 [11,12,2] 2 12 14 14
5 [12,15,2] 4 19 14 19
6 [13,18,1] 4 20 19 20

Final answer:

20

Complexity Analysis

Measure Complexity Explanation
Time O(m log m) Sorting and binary searching for each ride
Space O(m) DP array and end positions array

Here, m is the number of rides.

Sorting the rides dominates part of the runtime and costs O(m log m). Then, for each ride, we perform one binary search, which also costs O(log m) each. Since there are m rides, the total runtime remains O(m log m).

The space complexity is linear because we store:

  • The DP array
  • The sorted end positions array

Both require O(m) memory.

Test Cases

from typing import List

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        from bisect import bisect_right

        rides.sort(key=lambda ride: ride[1])

        ends = [ride[1] for ride in rides]

        m = len(rides)
        dp = [0] * (m + 1)

        for i in range(1, m + 1):
            start, end, tip = rides[i - 1]

            profit = end - start + tip

            compatible_index = bisect_right(ends, start, hi=i - 1)

            dp[i] = max(
                dp[i - 1],
                dp[compatible_index] + profit
            )

        return dp[m]

solution = Solution()

assert solution.maxTaxiEarnings(
    5,
    [[2,5,4],[1,5,1]]
) == 7  # provided example 1

assert solution.maxTaxiEarnings(
    20,
    [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
) == 20  # provided example 2

assert solution.maxTaxiEarnings(
    10,
    [[1,2,1],[2,3,1],[3,4,1]]
) == 6  # perfectly chainable rides

assert solution.maxTaxiEarnings(
    10,
    [[1,10,5],[2,3,100]]
) == 101  # smaller ride more profitable

assert solution.maxTaxiEarnings(
    10,
    [[1,3,1],[1,4,10],[1,5,2]]
) == 13  # overlapping rides with same start

assert solution.maxTaxiEarnings(
    10,
    [[1,3,1],[3,5,1],[5,7,1]]
) == 9  # rides sharing endpoints

assert solution.maxTaxiEarnings(
    100,
    [[1,100,1]]
) == 100  # single ride covering entire range

assert solution.maxTaxiEarnings(
    10,
    [[1,2,100],[2,10,1]]
) == 110  # chaining after large tip ride

assert solution.maxTaxiEarnings(
    10,
    [[1,5,1],[2,6,100],[6,10,1]]
) == 110  # choose optimal overlap combination
Test Why
Example 1 Validates basic overlapping choice
Example 2 Validates chaining compatible rides
Perfectly chainable rides Ensures endpoint compatibility works
Small profitable ride Ensures algorithm does not greedily choose longest ride
Same start rides Tests overlapping intervals with shared start
Shared endpoints Verifies rides can connect exactly
Single ride Smallest meaningful ride set
Large tip chain Tests profit accumulation
Overlap optimization Validates DP correctness

Edge Cases

One important edge case occurs when rides share endpoints. For example, one ride may end exactly where another begins. A common mistake is treating these rides as overlapping. The problem explicitly allows this transition, so the binary search must use <= start compatibility logic. Using bisect_right correctly handles this case.

Another important edge case is when a long ride appears attractive but several shorter rides together produce more profit. A greedy strategy based on ride length or immediate profit would fail here. The DP approach avoids this issue because it systematically compares all compatible combinations.

A third edge case involves many rides sharing the same end point. If the implementation incorrectly handles sorting or binary search boundaries, it may skip valid transitions or double count rides. Using sorted end positions and carefully limiting the binary search range ensures correctness even when multiple rides end at identical positions.