Car Fleet
MediumStack
There are n cars on a one-lane road, all driving in the same direction toward a destination at mile target. Car i starts at mile position[i] and drives at a constant speed[i] miles per hour.
Cars cannot pass each other. When a faster car catches up to a slower car (or group of cars) ahead of it, it slows down and from then on travels right behind it at the same speed. A group of cars traveling together like this is a fleet; a single car on its own is also a fleet.
If a car catches up to a fleet exactly at target, it still counts as part of that fleet.
Return the number of fleets that arrive at target.
Example 1
- Input:
- target = 15, position = [5, 3, 12, 1], speed = [2, 3, 1, 4]
- Output:
- 2
- Explanation
- On their own the cars would arrive at times 5, 4, 3 and 3.5. The car at 12 is in front and arrives first, alone. The car at 5 would arrive at time 5, later than the cars behind it, so the cars at 3 and 1 catch it and arrive together: 2 fleets.
Example 2
- Input:
- target = 10, position = [6, 8], speed = [2, 1]
- Output:
- 1
- Explanation
- The car at 6 needs 4 miles at speed 2 and the car at 8 needs 2 miles at speed 1, so both reach the target at time 2. Meeting exactly at the target still makes one fleet.
Example 3
- Input:
- target = 20, position = [2, 6, 10], speed = [2, 2, 2]
- Output:
- 3
- Explanation
- All cars drive at the same speed, so the gaps never close and each car arrives on its own.
Constraints
n == position.length == speed.length- 1 ≤
n≤ 105 - 0 <
target≤ 106 - 0 ≤
position[i]<target, and all positions are distinct - 0 <
speed[i]≤ 106