Car Fleet

Medium~30 min

There are n cars going to the same destination along a one-lane road. The destination is target miles away.

You are given two integer arrays position and speed, both of length n, where position[i] is the position of the ith car and speed[i] is the speed of the ith car (in miles per hour).

A car can never pass another car ahead of it, but it can catch up to it and drive at the same speed as the car ahead. The faster car will slow down to match the slower car's speed.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it is still considered one car fleet.

Return the number of car fleets that will arrive at the destination.

Examples

Example 1
Input: target = 12, position = [10, 8, 0, 5, 3], speed = [2, 4, 1, 1, 3]
Output: 3
Explanation: The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting at 12. The car starting at 0 (speed 1) does not catch anyone. The cars starting at 5 (speed 1) and 3 (speed 3): the car at 3 catches up to the car at 5 at position 6, forming a fleet. So there are 3 fleets.
Example 2
Input: target = 10, position = [3], speed = [3]
Output: 1
Example 3
Input: target = 100, position = [0, 2, 4], speed = [4, 2, 1]
Output: 1
Explanation: The cars starting at 0 (speed 4) catches up to the car at 2 (speed 2) and then both catch up to the car at 4 (speed 1). All form one fleet.

Constraints

  • n == position.length == speed.length
  • 1 <= n <= 10^5
  • 0 < target <= 10^6
  • 0 <= position[i] < target
  • All positions are unique
  • 0 < speed[i] <= 10^6
  • Expected time complexity: O(n log n)
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run