algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

maximum-earnings-from-taxi-v1.py (1033B)

      1 def start(e):
      2     return e[0]
      3 class Solution:
      4     def best_from(self,current_ride_index,rides):
      5 
      6         if current_ride_index in self.mem:
      7             return self.mem[current_ride_index]
      8         
      9         if current_ride_index >= len(rides):
     10             return 0
     11         
     12         ride = rides[current_ride_index]
     13         ending = ride[1]
     14         best_without = self.best_from(current_ride_index+1,rides)
     15 
     16         n_idx = current_ride_index+1
     17         for i in range(current_ride_index+1, len(rides) + 1):
     18             if i >= len(rides):
     19                 n_idx = i
     20                 break
     21             if rides[i][0] >= ending:
     22                 n_idx = i
     23                 break
     24             
     25         best_with = self.best_from(n_idx, rides)
     26 
     27         res = max(best_with + (ride[1] - ride[0]) + ride[2], best_without)
     28         self.mem[current_ride_index] = res
     29         return res
     30 
     31 
     32     def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
     33         rides.sort(key=start)
     34         self.mem = {}
     35         return self.best_from(0,rides)