Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution:
- def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
- # How to solve it:
- # Consider the closest car fleet first. The cars behind it will either catch up
- # to it or not. If they do catch up to it, you can consider the third car fleet
- # (just keep going back).
- # The car fleet closest to the target will arrive in (target - position) / speed
- # hours. The second car fleet will catch up to the closest car fleet in
- # (position[-1] - position[-2]) / (speed[-2] - speed[-1]) hours.
- def car_will_catch_up(r, l):
- closer_car_will_arrive_in_x_hours = (target - position[l]) / speed[l]
- further_car_will_catch_up_in_y_hours = (position[l] - position[r]) / (speed[r] - speed[l])
- if further_car_will_catch_up_in_y_hours < 0:
- return False
- if further_car_will_catch_up_in_y_hours <= closer_car_will_arrive_in_x_hours:
- return True
- num_fleets_arriving = 0
- arrived_cars = set()
- i = len(position) - 1
- while i >= 0:
- if i in arrived_cars:
- i -= 1
- continue
- current_fleet = set([i])
- j = i - 1
- while j >= 0:
- if car_will_catch_up(j, i):
- current_fleet.add(j)
- else:
- break
- j -= 1
- num_fleets_arriving += 1
- arrived_cars.update(current_fleet)
- i -= 1
- return num_fleets_arriving
Advertisement
Add Comment
Please, Sign In to add comment