1 to stops, always in one direction, from lower numbers to higher ones. There are orders orders, where orders[i] = [from, to, bonus] means a passenger wants a ride from stop from to stop to and will pay an extra bonus.
Each passenger carried earns the driver to - from + bonus. Only one passenger can ride at a time, but the driver may drop someone off and pick up the next passenger at the same stop.
Return the most money the driver can earn by choosing orders wisely.stops=8, orders=[[1, 4, 2], [3, 8, 1], [4, 6, 5]] → 12
Carry the first passenger from 1 to 4 (3 + 2 = 5), then at stop 4 pick up the third one to 6 (2 + 5 = 7), for 12 in total. The second order (5 + 1 = 6) overlaps both and does not pay off.
stops=10, orders=[[1, 10, 1], [2, 3, 1], [5, 7, 1]] → 10
The long ride pays 9 + 1 = 10, while the two short ones together pay 2 + 3 = 5, so the long one wins.
stops ≤ 10⁵orders.length ≤ 3 · 10⁴orders[i].length = 3from < to ≤ stopsbonus ≤ 10⁵stops=8, orders=[[1, 4, 2], [3, 8, 1], [4, 6, 5]]
12
Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.