Maximize a Cab Driver's Earnings Along a One-Way Route
A cab drives east through n numbered points in a metro corridor. Each ride request starts at one point, ends at a later point, and pays the fare plus a tip in rupees. The cab can carry one rider at a time and only moves east. Maximize total earnings.
Problem
There are n points (1..n) along a one-way road heading east. rides[i] = [start, end, tip] means a passenger goes from start to end (start < end) paying (end - start) + tip rupees. You drive east picking up non-overlapping rides (a ride ending at x lets you start another at x). Return the maximum rupees you can earn.
Input
An integer n and a rides list of [start, end, tip].
Output
An integer: the maximum total earnings in rupees.
Constraints
- 1 <= n <= 10^5
- 1 <= rides.length <= 3*10^4
- 1 <= start < end <= n, 1 <= tip <= 10^5.
Examples
Example 1
Input
n = 5, rides = [[2,5,4],[1,5,1]]
Output
7
Taking [2,5,4] earns (5-2)+4 = 7, better than [1,5,1]'s 5.
Example 2
Input
n = 20, rides = [[1,6,1],[3,10,2],[10,12,3],[11,12,2],[12,15,2],[13,18,1]]
Output
20
An optimal chain of compatible rides totals 20 rupees.