Car Fleet
There are n cars going to the same destination along a one-lane road. The cars have different speeds and fuel efficiency. Each car is represented by an array of two elements: the position of the car and its speed. The position is the distance from the destination, and the speed is the speed of the car. A car fleet is a group of cars that will arrive at the destination at the same time. Write a function to find the number of car fleets that will arrive at the destination.
Constraints:
- 1 <= n <= 10^5
- 1 <= position, speed <= 10^6
Examples:
Input: [[1, 2], [2, 1], [4, 3], [7, 2]]
Output: 3
Explanation: The first car fleet consists of the first car, the second car fleet consists of the second car, and the third car fleet consists of the third and fourth cars.
Solutions
Sorting and Greedy Algorithm
The solution first sorts the cars based on their positions in descending order. Then it iterates over the sorted cars and calculates the time it takes for each car to reach the target. If the time is greater than the maxTime, it increments the fleet count and updates the maxTime.
public int carFleet(int target, int[] position, int[] speed) {
int n = position.length;
int[][] cars = new int[n][2];
for (int i = 0;
i < n;
i++) {
cars[i][0] = position[i];
cars[i][1] = speed[i];
}
Arrays.sort(cars, (a, b) -> b[0] - a[0]);
int fleets = 0;
double maxTime = 0;
for (int i = 0;
i < n;
i++) {
double time = (double) (target - cars[i][0]) / cars[i][1];
if (time > maxTime) {
fleets++;
maxTime = time;
}
}
return fleets;
}Follow-up:
What if the cars have different fuel efficiencies?
