LeetCode 853: Car Fleet
Problem Description
Explanation
To solve this problem, we can simulate the car fleets moving towards the target mile. We can sort the cars based on their starting positions. Then, starting from the last car, we calculate the time taken by each car to reach the target mile. If a car reaches the target before the car in front of it, they form a fleet. Otherwise, they are separate fleets. We keep track of the fleet count.
Time Complexity: O(n log n) due to sorting
Space Complexity: O(n)
Solutions
class Solution {
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) -> Integer.compare(b[0], a[0]));
int fleets = 0;
double time = -1;
for (int i = 0; i < n; i++) {
double arrivalTime = (double) (target - cars[i][0]) / cars[i][1];
if (arrivalTime > time) {
time = arrivalTime;
fleets++;
}
}
return fleets;
}
}Related LeetCode Problems
Loading editor...