Car Fleet

Sort cars from closest to the target to farthest. A car's independent arrival time is (target - position) / speed. Scan in that order while retaining the largest arrival time among fleets already ahead. If the current car's time is less than or equal to that value, it catches the fleet ahead before the target and inherits that fleet time; otherwise it starts a new fleet and becomes the new maximum. Use floating-point or compare fractions carefully if precision matters. The important invariant is that fleet arrival times encountered from front to back are strictly increasing. Do not simulate positions over time. Sorting dominates at O(n log n) time; the scan is O(n), with O(n) storage for pairs or O(1) extra beyond sorting in place.