Approach 1: Sort
Call the "lead fleet" the fleet furthest in position.
If the car
S (Second) behind the lead car
F (First) would arrive earlier, then
S forms a fleet with the lead car
F. Otherwise, fleet
F is final as no car can catch up to it - cars behind
S would form fleets with
A car is a
(position, speed) which implies some arrival time
(target - position) / speed. Sort the cars by position.
Now apply the above reasoning - if the lead fleet drives away, then count it and continue. Otherwise, merge the fleets and continue.
Time Complexity: , where is the number of cars. The complexity is dominated by the sorting operation.
Space Complexity: , the space used to store information about the cars.
Analysis written by: @awice.