algorithms

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

maximum-earnings-from-taxi-v2.py (1225B)

      1 def start(e):
      2     return e[0]
      3 class Solution:
      4 
      5     def binary_search_find(self, rides, left, right, target):
      6         while left < right:
      7             mid = left + (right - left) // 2
      8             if rides[mid][0] < target:
      9                 left = mid + 1
     10             else:
     11                 right = mid
     12         if left < len(rides) and rides[left][0] >= target:
     13             return left
     14         return -1
     15 
     16 
     17     def best_from(self,current_ride_index,rides):
     18 
     19         if current_ride_index in self.mem:
     20             return self.mem[current_ride_index]
     21         
     22         if current_ride_index >= len(rides) or current_ride_index == -1:
     23             return 0
     24         
     25         ride = rides[current_ride_index]
     26         ending = ride[1]
     27         best_without = self.best_from(current_ride_index+1,rides)
     28 
     29         n_idx = self.binary_search_find(rides,current_ride_index,len(rides)-1,ride[1])
     30         best_with = self.best_from(n_idx, rides)
     31 
     32         res = max(best_with + (ride[1] - ride[0]) + ride[2], best_without)
     33         self.mem[current_ride_index] = res
     34         return res
     35 
     36 
     37     def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
     38         rides.sort(key=start)
     39         self.mem = {}
     40         return self.best_from(0,rides)