Recently little Dom likes to play with all kinds of toy cars. Some toy cars run fast and some toy cars run slowly. Little Dom was curious to know how to make two toy cars to get there at the same time.

To help Little Dom solve this problem, today we are going to look at the algorithmic “fleet” problem.

The rules for “fleet” questions are as follows:

  • N cars travel down one lane to a common destination miles away from Target.
  • Each car I travels along the lane to the destination from its initial position[I] (miles) at a constant speed of speed[I] (miles).
  • A car never passes another car in front of it, but it can catch up and follow at the same speed as the car in front.
  • At this point, we ignore the distance between the two cars, that is, they are assumed to be in the same position.
  • A fleet is a non-empty collection of cars traveling at the same speed at the same location. Note that a car can also be a fleet of cars.
  • Even if a vehicle catches up with a convoy at its destination, they are still considered the same convoy.

Dom needs to figure out how many teams will arrive at their destination?

Example 1 is as follows:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] output: 3 explanation: cars starting at 10 and 8 form a convoy and meet at 12. A car starting at zero can't catch up with other cars, so it's a team by itself. Cars starting at 5 and 3 form a convoy, and they meet at 6. Please note that no other cars will meet these convoys until they reach their destination, so the answer is 3.Copy the code

Example 2 is as follows:

Input: target = 20, position = [6,2,17], speed = [3,9,2] output: 2 The car that starts at 17th can't be caught, so it's a caravan all by itself. Please note that no other cars will meet these convoys until they reach their destination, so the answer is 2.Copy the code

This is the “fleet” problem in the algorithm. Do you, the smart one, know how to help Little Dom solve this problem?