Car Fleet medium

Problem Statement

You are given an integer target representing the target speed, and two integer arrays position and speed of the same length. Each position[i] and speed[i] represent the position and speed of the i-th car. A car can only move in one direction (forward). A fleet is defined as a group of cars that can reach the target at the same time. Return the number of fleets that will arrive at the target.

Notes:

• Cars can pass each other.
• The positions are sorted in ascending order.

Example 1

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] Output: 3 Explanation: The cars are at positions [10,8,0,5,3] and have speeds [2,4,1,1,3]. Cars can reach the target at following times:

• Car 1: (12-10)/2 = 1
• Car 2: (12-8)/4 = 1
• Car 3: (12-0)/1 = 12
• Car 4: (12-5)/1 = 7
• Car 5: (12-3)/3 = 3

The cars will reach the target at times [1,1,12,7,3]. The times are sorted to [1,1,3,7,12]. Since the cars at positions 10, 8 and 5 arrive together, we only count them once (fleet 1). The car at position 3 forms another fleet (fleet 2). And the car at position 0 forms a third fleet (fleet 3). Therefore, there are 3 fleets.

Example 2

Input: target = 10, position = [3], speed = [3] Output: 1 Explanation: There is only one car, so there is only one fleet.

Steps

1. Calculate arrival times: For each car, calculate the time it takes to reach the target using the formula (target - position[i]) / speed[i].
2. Sort cars by arrival time: Sort the cars in ascending order based on their arrival times.
3. Count fleets: Iterate through the sorted cars. If a car's arrival time is greater than the arrival time of the previous car, it forms a new fleet. Otherwise, it joins the existing fleet.

Explanation

The key idea is that cars that arrive at the same time or nearly the same time form a fleet. Sorting by arrival time allows us to efficiently group cars into fleets. If a car's arrival time is strictly greater than the previous car's arrival time, it means it will arrive later and will not catch up to the previous fleet. Hence, it forms a new fleet.

Code

#include <vector>
#include <algorithm>

using namespace std;

int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int n = position.size();
    if (n == 0) return 0;

    // Create a vector of pairs (position, speed)
    vector<pair<int, int>> cars(n);
    for (int i = 0; i < n; ++i) {
        cars[i] = {position[i], speed[i]};
    }

    // Sort cars by position in ascending order
    sort(cars.begin(), cars.end());

    // Calculate arrival times
    vector<double> arrivalTimes(n);
    for (int i = 0; i < n; ++i) {
        arrivalTimes[i] = (double)(target - cars[i].first) / cars[i].second;
    }

    // Count fleets
    int fleets = 1;
    double lastArrivalTime = arrivalTimes[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        if (arrivalTimes[i] > lastArrivalTime) {
            fleets++;
            lastArrivalTime = arrivalTimes[i];
        }
    }

    return fleets;
}

Complexity

• Time Complexity: O(N log N), dominated by the sorting step.
• Space Complexity: O(N) to store arrival times and pairs of position and speed.