853.Car Fleet | zhengxingxing

Method 1

There are n cars at given miles away from the starting mile 0, traveling to reach the mile target.
You are given two integer array 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.

Example 1

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Output: 3

Explanation:

The cars starting at 10 (speed 2) and 8 (speed 4) become a fleet, meeting each other at 12. The fleet forms at target.
The car starting at 0 (speed 1) does not catch up to any other car, so it is a fleet by itself.
The cars starting at 5 (speed 1) and 3 (speed 3) become a fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Example 2

Input: target = 10, position = [3], speed = [3]

Output: 1

Explanation:

There is only one car, hence there is only one fleet.

Example 3

Input: target = 100, position = [0,2,4], speed = [4,2,1]

Output: 1

Explanation:

The cars starting at 0 (speed 4) and 2 (speed 2) become a fleet, meeting each other at 4. The car starting at 4 (speed 1) travels to 5.
Then, the fleet at 4 (speed 2) and the car at position 5 (speed 1) become one fleet, meeting each other at 6. The fleet moves at speed 1 until it reaches target.

Method 1

【O(n log n) time | O(n) space】

package Leetcode.Stack;

import java.util.*;

/**
 * @author zhengstars
 * @date 2024/10/11
 */
public class CarFleet {
    public static int carFleet(int target, int[] position, int[] speed) {
        // Create a map to store the time each car takes to reach the target
        // Key: initial position, Value: time to reach target
        Map<Integer, Double> map = new HashMap<>();

        // Calculate and store the time for each car to reach the target
        for (int i = 0; i < position.length; i++) {
            // Time = (target distance - initial position) / speed
            map.put(position[i], (target - position[i]) / (double)speed[i]);
        }

        // Sort the positions in ascending order
        // This allows us to process cars from front to back
        Arrays.sort(position);

        // Use a stack to keep track of car fleets
        // Each element in the stack represents the arrival time of a fleet
        Deque<Double> stack = new ArrayDeque<>();

        // Iterate through positions from back to front (rightmost to leftmost)
        for (int i = position.length - 1; i >= 0 ; i--) {
            // If the current car reaches the target earlier or at the same time as the car in front,
            // it will join that fleet, so we skip it (don't add to stack)
            if(!stack.isEmpty() && map.get(position[i]) <= stack.peek()){
                continue;
            }
            // If the current car reaches later, it forms a new fleet, so we add it to the stack
            stack.push(map.get(position[i]));
        }

        // The number of elements in the stack represents the number of fleets
        return stack.size();
    }

    // Test cases
    public static void main(String[] args) {
        // Test case 1
        int target1 = 12;
        int[] position1 = {10,8,0,5,3};
        int[] speed1 = {2,4,1,1,3};
        System.out.println("Test case 1 result: " + carFleet(target1, position1, speed1)); // Expected output: 3

        // Test case 2
        int target2 = 10;
        int[] position2 = {3};
        int[] speed2 = {3};
        System.out.println("Test case 2 result: " + carFleet(target2, position2, speed2)); // Expected output: 1

        // Test case 3
        int target3 = 100;
        int[] position3 = {0,2,4};
        int[] speed3 = {4,2,1};
        System.out.println("Test case 3 result: " + carFleet(target3, position3, speed3)); // Expected output: 1
    }
}

Method 1

Enjoy Reading This Article?