Problem Description

There are n cars traveling to the same destination on a one-lane highway.

You are given two arrays of integers position and speed, both of length n.

• position[i] is the position of the ith car (in miles).
• speed[i] is the speed of the ith car (in miles per hour).

The destination is at position target miles.

A car can not pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.

A car fleet is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.

If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.

Return the number of different car fleets that will arrive at the destination.

Example 1:

Input: target = 10, position = [1,4], speed = [3,2]
Output: 1
Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.

Example 2:

Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]
Output: 3
Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.

Constraints:

• n == position.length == speed.length
• 1 <= n <= 1000
• 0 < target <= 1000
• 0 < speed[i] <= 100
• 0 <= position[i] < target
• All the values of position are unique.

Approach

Use a TreeMap to store the positions and speeds of the cars, naturally sorting them by position. Then, iterate through the cars from the closest to the destination from the end. At each step, calculate the time it takes for the current car to reach the destination ((target - position) / speed). If this time is greater than the time it takes for the fleet ahead of it (represented by the top of the stack), it means this car will not catch up and thereby forms a new fleet. We push its position onto the stack. If the time is less than or equal, the car will catch up and join the fleet ahead, so we do nothing. The final size of the stack represents the number of car fleets.

Solution

class Solution {
    public int carFleet(int target, int[] position, int[] speed) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = position.length;
        for(int i=0;i<n;i++){
            map.put(position[i], speed[i]);
        }
        int[][] matrix = new int[n][2];
        int index = 0;
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            matrix[index][0] = entry.getKey();
            matrix[index][1] = entry.getValue();
            index++;
        }
        Stack<Integer> st = new Stack<>();
        st.push(matrix[n-1][0]);
        for(int i=n-2;i>=0;i--){
            double timep = (double)(target-st.peek())/map.get(st.peek());
            double timec = (double)(target-matrix[i][0])/matrix[i][1];
            if(timec>timep){
                st.push(matrix[i][0]);
            }
        }
        return st.size();
    }
}