Car Fleet

• Create a list of custom Car objects, where each object stores a car's position and its calculated time to reach the target. The time is (target - position) / speed.
• Sort this list of cars in ascending order of their positions.
• Use a while loop that continues as long as merges occur in a pass.
• Inside the loop, iterate through the cars from second-to-last to the first (i from n-2 down to 0).
• If the arrival time of car i is less than or equal to the arrival time of car i+1 (the one in front), it means car i merges into the fleet of i+1.
• To handle the merge, remove car i from the list. Set a flag indicating a merge occurred and break the inner loop to restart the scan from the beginning of the modified list.
• If the while loop completes a full pass over the cars without any merges, the fleets are stable. The loop terminates.
• The final number of fleets is the size of the remaining list of cars.

The core idea is to directly simulate the physical process. After sorting the cars by position, we know their relative order. A car can only merge with the one directly ahead of it. We can use a dynamic list of cars and iterate through it. If we find a car i that will catch up to car i+1 (meaning time[i] <= time[i+1]), we merge them by removing car i. Since this merge could cause the car previously at i-1 to now be able to merge with the fleet at i+1, we must restart our scan. This process is repeated until a full scan of all cars results in no merges, indicating that the final fleet configuration has been reached.

1class Car {2    int position;3    double time;4    Car(int p, double t) {5        this.position = p;6        this.time = t;7    }8}9 10public int carFleet(int target, int[] position, int[] speed) {11    if (position.length <= 1) return position.length;12    List<Car> cars = new ArrayList<>();13    for (int i = 0; i < position.length; i++) {14        cars.add(new Car(position[i], (double)(target - position[i]) / speed[i]));15    }16    // Sort by position17    cars.sort(Comparator.comparingInt(a -> a.position));18 19    while (true) {20        boolean mergedInPass = false;21        for (int i = cars.size() - 2; i >= 0; i--) {22            // Car i is behind car i+123            if (cars.get(i).time <= cars.get(i+1).time) {24                // Car i merges into the fleet of car i+1.25                // The new fleet's arrival time is that of car i+1.26                // We can just remove car i.27                cars.remove(i);28                mergedInPass = true;29                // Restart scan since the list has changed30                break; 31            }32        }33        if (!mergedInPass) {34            break; // No merges in a full pass, we are done.35        }36    }37    return cars.size();38}

• Create an array of Car objects, each storing a position and speed.
• Sort this array of cars based on their starting position in ascending order.
• Initialize a fleets counter to 0 and a leadTime variable to track the arrival time of the current leading fleet (initialized to -1.0 or 0.0).
• Iterate through the sorted cars in reverse order, from the car closest to the target (n-1) to the one furthest away (0).
• For each car, calculate its individual arrival time: currentTime = (target - position) / speed.
• Compare currentTime with leadTime:
  • If currentTime > leadTime, it means this car is slower than the fleet ahead of it and cannot catch up. It must form a new fleet. Increment fleets and update leadTime to currentTime, as this car is now the new bottleneck for any cars behind it.
  • If currentTime <= leadTime, this car is fast enough to catch the fleet ahead. It merges into that fleet. No changes are needed for fleets or leadTime.
• After the loop completes, return the final fleets count.

The logic is that if car A is behind car B, they form a fleet only if car A can catch up to car B before or at the target. This is equivalent to saying that the time it would take car A to reach the target (if unobstructed) is less than or equal to the time it would take car B.

By sorting the cars by position, we can iterate from the one closest to the target backwards. The car closest to the target is always the leader of a fleet. We record its arrival time. Then, for the next car behind it, we check if its arrival time is less than or equal to the leader's time. If it is, it merges. If it's greater, it's too slow and forms a new fleet, becoming the new 'leader' for the cars behind it. This process continues, maintaining the arrival time of the slowest fleet currently at the front. This is a form of monotonic stack logic, where the arrival times of the fleet leaders we identify will be strictly increasing.

1class Car {2    int position;3    int speed;4    Car(int p, int s) {5        this.position = p;6        this.speed = s;7    }8}9 10public int carFleet(int target, int[] position, int[] speed) {11    int n = position.length;12    if (n <= 1) {13        return n;14    }15 16    Car[] cars = new Car[n];17    for (int i = 0; i < n; i++) {18        cars[i] = new Car(position[i], speed[i]);19    }20 21    // Sort cars by position in ascending order22    Arrays.sort(cars, (a, b) -> Integer.compare(a.position, b.position));23 24    int fleets = 0;25    double leadTime = -1.0; // Arrival time of the current fleet leader26 27    // Iterate from the car closest to the target backwards28    for (int i = n - 1; i >= 0; i--) {29        double currentTime = (double)(target - cars[i].position) / cars[i].speed;30        if (currentTime > leadTime) {31            // This car is slower than the fleet in front of it,32            // so it becomes the leader of a new fleet.33            fleets++;34            leadTime = currentTime;35        }36        // Otherwise, this car will catch up and merge with the fleet ahead.37        // The number of fleets and the leadTime do not change.38    }39 40    return fleets;41}