Show problems as
Classic problem #2008MediumArrayHash TableBinary SearchDynamic ProgrammingSorting

Maximum Earnings From Taxi

Real-world version: Booking the Tram Along the Line
Tracked in this browser only
Read Maximum Earnings From Taxi on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_taxi_earnings(n: int, requests: list[list[int]]) -> int:
Java
public long maxTaxiEarnings(int n, int[][] requests)

More on the same topics