Car Fleet
n cars drive along a one-lane road toward a destination at mile target. Car i starts at mile position[i] (all distinct) with speed speed[i]. Cars cannot pass each other: when a faster car catches up to a slower one, it slows to match and they travel together as a fleet (one clump of cars at the same position). A fleet's speed is the slowest member's. If a car catches another exactly at the destination, they still count as one fleet.
Return how many fleets arrive at the destination. Up to 10^5 cars, so the intended solution sorts once and then works in a single pass.
Examples
- Input:
- target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
- Output:
- 3
The car at 10 (speed 2) reaches mile 12 in 1 time unit; the car at 8 (speed 4) would also arrive at time 1, so it catches the slower car exactly at the target — one fleet. The car at 0 never catches anyone: fleet two. Cars at 5 and 3: the one at 3 (speed 3) catches the one at 5 (speed 1) before mile 12 and slows to match: fleet three.
- Input:
- target = 10, position = [3], speed = [3]
- Output:
- 1
A single car is a single fleet.
- Input:
- target = 100, position = [0,2,4], speed = [4,2,1]
- Output:
- 1
The car at 4 is slowest; the car at 2 catches it, then the car at 0 catches them both. Everyone merges into one fleet before mile 100.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.