1087MediumArrayHash TableBinary SearchDynamic ProgrammingSorting

Booking the Tram Along the Line

Tracked in this browser only

Trains the technique from

LeetCode 2008Maximum Earnings From Taxi

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tram runs along a line of n stops numbered 1 through n, and it only ever travels forwards.

requests[i] = [from, to, bonus] is a booking asking the tram to carry a party from stop from to stop to, paying to - from + bonus coins.

The tram may accept any collection of bookings so long as no two of them overlap. Two bookings do not overlap when one of them ends at or before the other begins, so a party may be set down at the very stop where the next party gets on.

Return the most coins the tram can earn.

Examples

Example 1

Input: n = 4, requests = [[1, 2, 1], [2, 4, 1]]
Output: 5

The first party rides one stop and adds a bonus of 1, paying 2 coins. The second gets on at the very stop the first got off, rides two stops and adds a bonus of 1, paying 3 coins. Together that is 5.

Example 2

Input: n = 10, requests = [[1, 10, 1], [1, 5, 1], [5, 10, 1]]
Output: 11

Carrying one party the whole way pays 10 coins. Splitting the line into two hops pays 5 and then 6, so 11 coins, and the two hops meet at a single stop so they are allowed.

Example 3

Input: n = 10, requests = [[1, 2, 1], [3, 4, 1], [5, 6, 1], [7, 8, 1], [9, 10, 1], [1, 10, 3]]
Output: 12

The five short bookings pay 2 coins each, 10 in all. The one long booking pays 9 for the distance plus a bonus of 3, which is 12, and it clashes with every other booking.

Constraints

1 <= n <= 10^5
1 <= requests.length <= 3 * 10^4
requests[i].length == 3
1 <= requests[i][0] <= n
1 <= requests[i][1] <= n
requests[i][0] < requests[i][1]
1 <= requests[i][2] <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_taxi_earnings(n: int, requests: list[list[int]]) -> int:

Java

public long maxTaxiEarnings(int n, int[][] requests)

The intended approach

Time O(n + m) over the stops and the bookings.Space O(n + m) for the per-stop numbers and the grouping.

Sweep the line from the first stop to the last and keep one number per stop: the most coins earnable by a tram that has finished all its accepted work by that stop. At stop `s` there are only two kinds of plan. Either nothing ends exactly at `s`, in which case the best is whatever was best at stop `s - 1`, or some booking ends at `s`, and then that booking's party got on at its own starting stop, which means everything before it had to be wrapped up by then. So the plan is worth the best at that booking's starting stop plus the booking's own fare. Taking the largest of those candidates settles stop `s`. That needs the bookings grouped by where they end, which one pass over the list arranges. Because the rule lets a booking end exactly where the next begins, the lookup is the starting stop itself and not the stop before it. The answer sits at the last stop, and the running numbers never fall, so no separate maximum is needed.

Pythonentry point: max_taxi_earnings

def max_taxi_earnings(n, requests):
    ending = [[] for _ in range(n + 1)]
    for booking in requests:
        ending[booking[1]].append(booking)
    best = [0] * (n + 1)
    for stop in range(1, n + 1):
        top = best[stop - 1]
        for booking in ending[stop]:
            take = best[booking[0]] + booking[1] - booking[0] + booking[2]
            if take > top:
                top = take
        best[stop] = top
    return best[n]

The obvious version

Try every collection of bookings as a bit pattern. Sort the chosen bookings by where they start, walk through them checking that each one begins at or after the previous one ended, and total the fares of the collections that hold up. Costs two to the power of the booking count.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_taxi_earnings(n, requests):
    m = len(requests)
    best = 0
    for mask in range(1 << m):
        chosen = []
        for i in range(m):
            if mask & (1 << i):
                chosen.append(requests[i])
        chosen.sort(key=lambda booking: booking[0])
        total = 0
        reach = 0
        ok = True
        for booking in chosen:
            if booking[0] < reach:
                ok = False
                break
            total += booking[1] - booking[0] + booking[2]
            reach = booking[1]
        if ok and total > best:
            best = total
    return best

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in