nathanwailes

LeetCode 853 - Car Fleet - 2022.12.27 solution

Dec 27th, 2022
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.58 KB | None | 0 0
  1. class Solution:
  2.     def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
  3.         # How to solve it:
  4.         # Consider the closest car fleet first.  The cars behind it will either catch up
  5.         # to it or not.  If they do catch up to it, you can consider the third car fleet
  6.         # (just keep going back).
  7.         # The car fleet closest to the target will arrive in (target - position) / speed
  8.         # hours.  The second car fleet will catch up to the closest car fleet in
  9.         # (position[-1] - position[-2]) / (speed[-2] - speed[-1]) hours.
  10.  
  11.         def car_will_catch_up(r, l):
  12.             closer_car_will_arrive_in_x_hours = (target - position[l]) / speed[l]
  13.             further_car_will_catch_up_in_y_hours = (position[l] - position[r]) / (speed[r] - speed[l])
  14.             if further_car_will_catch_up_in_y_hours < 0:
  15.                 return False
  16.             if further_car_will_catch_up_in_y_hours <= closer_car_will_arrive_in_x_hours:
  17.                 return True
  18.  
  19.         num_fleets_arriving = 0
  20.         arrived_cars = set()
  21.         i = len(position) - 1
  22.         while i >= 0:
  23.             if i in arrived_cars:
  24.                 i -= 1
  25.                 continue
  26.             current_fleet = set([i])
  27.             j = i - 1
  28.             while j >= 0:
  29.                 if car_will_catch_up(j, i):
  30.                     current_fleet.add(j)
  31.                 else:
  32.                     break
  33.                 j -= 1
  34.             num_fleets_arriving += 1
  35.             arrived_cars.update(current_fleet)
  36.             i -= 1
  37.         return num_fleets_arriving
Advertisement
Add Comment
Please, Sign In to add comment