853. Car Fleet

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.

You are given two integer arrays, position and speed, both of length n, where position[i] is the starting mile of the ith car and speed[i] is the speed of the ith car in miles per hour. A car cannot pass another car, but it can catch up and then travel next to it at the speed of the slower car. A car fleet is a car or cars driving next to each other. The speed of the car fleet is the minimum speed of any car in the fleet. If a car catches up to a car fleet at the mile target, it will still be considered as part of the car fleet. Return the number of car fleets that will arrive at the destination.

 

The goal for this question was mathematically thinking how we should solve this problem. The question is simply asking whether these linear equations can intersect before the target(y-value). With the given initial position and speed, we can calculate the arrival time for each car. If the car with the furthest position from the target has a shorter arrival time than the car closer to the target, those cars meet before the target. Since the car further from the target has the higher speed, it has to slow down to go along with the other car. 

 

First, we have to sort the array in ascending order of the position. To find the car fleet, we traverse the array in reverse order. If the arrival time of the car is smaller than or equal to the current car, we count them up as a car fleet.