Maximum Earnings

Problem Statement

Maximum Earnings Problem Description A taxi driver knows the pick-up and drop-off locations of the people requesting a ride. All locations are measured in km from the starting point (0 km). For every km a passenger travels, the driver charges that passenger 1 unit of money. In addition, each passenger offers a tip, which the driver receives only if that passenger is accepted. The taxi can carry only one passenger at a time. The driver cannot backtrack. If a passenger is picked up at location 2 and dropped off at location 9, the driver cannot accommodate another passenger at locations 3 through 8. If the trips of two people overlap, at most one of them can be accepted. A passenger picked up at pickup[i] and dropped off at drop[i] earns the driver (drop[i] - pickup[i]) + tip[i] . Two trips overlap when they share some stretch of road of positive length. A trip may start exactly where another trip ends: a passenger picked up at location 9 can be accepted together with a passenger dropped