The problem
Cars drive along a one-lane road toward mile target. Car i starts at position[i] and drives at speed[i] miles per hour.
A car can never pass another. When it catches up with a slower car it slows down and they drive on together as one fleet (a car on its own is a fleet too). Catching up exactly at the target still counts as one fleet. How many fleets arrive?
Examples
- Input
target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
- Output
3
- Input
target = 10, position = [3], speed = [3]
- Output
1
- Input
target = 100, position = [0, 2, 4], speed = [4, 2, 1]
- Output
1
Constraints
- 1 ≤ n ≤ 10⁵
- 0 < target ≤ 10⁶
- 0 ≤ position[i] < target, all different
- 0 < speed[i] ≤ 10⁶
The idea
Only the car directly ahead matters, so take the cars in order of position, nearest the target first. Each would arrive, on its own, at time (target − position) ÷ speed.
If a car would arrive later than the fleet just ahead of it, it can never catch that fleet: it leads a new one. If it would arrive sooner or at the same moment, it catches up and simply joins — the fleet still arrives at the slower time. Count the new fleets.
- Time
- O(n log n) — sorting by position
- Space
- O(n)
Solution · every language run against every case
class Solution: def carFleet(self, target: int, position: List[int], speed: List[int]) -> int: cars = sorted(zip(position, speed), reverse=True) # nearest the target first fleets = 0 slowest = 0.0 # arrival time of the fleet just ahead for p, s in cars: t = (target - p) / s # when this car would arrive on its own if t > slowest: # it cannot catch the fleet ahead: a new fleet fleets += 1 slowest = t return fleets