Approach 1: Sort

Intuition

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 S, never F.

Algorithm

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.

Complexity Analysis

  • 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.