Tap here to switch tabs
Problem
Submissions

Problem: Maximum Earnings From Taxi

Maximum Earnings From Taxi asks you to select compatible rides between numbered road points, earning each passenger's travel distance plus tip, and return the greatest total earnings.

Statement

There are n points positioned along a road, numbered from 11 to n. You are given the integer n and a 2extD2 ext{D} integer array rides, where rides[i] = [start_i, end_i, tip_i] indicates that the iextthi^{ ext{th}} passenger wants to travel from point start_i to point end_i and will provide a tip of tip_i dollars.

If you choose to transport passenger ii, you earn (end_i −- start_i ++ tip_i) dollars. You can only carry at most 11 passenger at any given time. You can only move forward from smaller numbered points to larger numbered points. Dropping off a passenger at a point allows you to immediately pick up another passenger at that same point.

Return the maximum total earnings you can collect.

Constraints:

  • 1≤1 \le n ≤105\le 10^5

  • 1≤1 \le rides.length ≤3imes104\le 3 imes 10^4

  • rides[i].length =3= 3

  • 1≤1 \le start_i << end_i ≤\le n

  • 1≤1 \le tip_i ≤105\le 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximum Earnings From Taxi

Maximum Earnings From Taxi asks you to select compatible rides between numbered road points, earning each passenger's travel distance plus tip, and return the greatest total earnings.

Statement

There are n points positioned along a road, numbered from 11 to n. You are given the integer n and a 2extD2 ext{D} integer array rides, where rides[i] = [start_i, end_i, tip_i] indicates that the iextthi^{ ext{th}} passenger wants to travel from point start_i to point end_i and will provide a tip of tip_i dollars.

If you choose to transport passenger ii, you earn (end_i −- start_i ++ tip_i) dollars. You can only carry at most 11 passenger at any given time. You can only move forward from smaller numbered points to larger numbered points. Dropping off a passenger at a point allows you to immediately pick up another passenger at that same point.

Return the maximum total earnings you can collect.

Constraints:

  • 1≤1 \le n ≤105\le 10^5

  • 1≤1 \le rides.length ≤3imes104\le 3 imes 10^4

  • rides[i].length =3= 3

  • 1≤1 \le start_i << end_i ≤\le n

  • 1≤1 \le tip_i ≤105\le 10^5