Car Fleet
Medium · stack
Several cars drive along a single-lane road towards a finish line at mile target. You are given two lists of the same length: position[i] is the mile where car i starts (all starting miles are different, and all are before the finish line) and speed[i] is its constant speed in miles per hour.
Cars cannot overtake. If a faster car catches up with a slower car ahead of it, it slows down to the slower car's speed and from then on they drive bumper to bumper as one fleet. A fleet drives at the speed of its slowest car, and more cars can join it later. A single car on its own is also a fleet. A car that reaches a fleet exactly at the finish line is part of that fleet.
Return the number of different fleets that arrive at the finish line.
Examples
Example 1
Input: target = 20, position = [2, 6, 9, 14], speed = [3, 2, 1, 4]
Output: 2
The car at mile 14 reaches the line first, all alone. The cars at miles 6 and 2 would reach mile 9's car before it gets to the line, so they join it, forming a second fleet.
Example 2
Input: target = 10, position = [0, 4, 8], speed = [1, 1, 1]
Output: 3
Equal speeds never close the gaps, so each car arrives separately.
Example 3
Input: target = 10, position = [6, 2], speed = [1, 2]
Output: 1
The back car catches the front car exactly at the finish line, so they count as one fleet.
Constraints
- 1 <= len(position) == len(speed) <= 10^5
- 1 <= target <= 10^6
- 0 <= position[i] < target, and all values in position are different
- 1 <= speed[i] <= 10^6
- The cars in position are not necessarily given in order of position.