Car Fleet

There are n cars at different starting positions on a road that are moving toward the same target with different speeds. Cars traveling at the same speed or slower cars ahead of them can form fleets. Return the number of car fleets that will arrive at the destination. Example: Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] Output: 3 Explanation: Cars that catch up before the target travel as one fleet. Pattern focus: Monotonic Stack / Queue for ordered merging of arrival times.

Input Format

target, position, speed = destination, starting positions, and speeds

Output Format

number of fleets that reach the target

Constraints

• 1 <= position.length == speed.length <= 10^5
• 0 < position[i] < target <= 10^6
• 1 <= speed[i] <= 10^6

Examples

target = 12
position = [10,8,0,5,3]
speed = [2,4,1,1,3]

3

target = 10
position = [3]
speed = [3]

1