Lecture 162:-Car Fleet

The "Car Fleet" problem is a classic problem in which you need to determine the number of car fleets that can reach a target destination.

Here's the problem statement:

N cars are going to the same destination along a one-lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it and drive bumper to bumper at the same speed.

The distance between these two cars is distance[i] = target - position[i].

The time it takes for the i-th car to reach the target is time[i] = distance[i] / speed[i].

We need to find out how many car fleets will reach the destination. A fleet is some non-empty set of cars driving at the same speed that arrive at the destination at the same time.

Here's a C++ implementation to solve the "Car Fleet" problem:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> int carFleet(int target, std::vector<int>& position, std::vector<int>& speed) { int n = position.size(); if (n == 0) { return 0; } std::vector<std::pair<int, double>> cars; for (int i = 0; i < n; ++i) { int dist = target - position[i]; double time = static_cast<double>(dist) / speed[i]; cars.push_back({position[i], time}); } std::sort(cars.begin(), cars.end()); int fleets = 1; double currTime = cars[n - 1].second; for (int i = n - 2; i >= 0; --i) { if (cars[i].second > currTime) { ++fleets; currTime = cars[i].second; } } return fleets; } int main() { int target = 12; std::vector<int> position = {10, 8, 0, 5, 3}; std::vector<int> speed = {2, 4, 1, 1, 3}; int fleets = carFleet(target, position, speed); std::cout << "Number of Car Fleets: " << fleets << std::endl; return 0; }

In this example, the carFleet function calculates the number of car fleets that will reach the destination based on the given positions and speeds of the cars. The main function demonstrates how to use this function for a specific input.

For the given input, the output will be:

javascriptCopy code

Number of Car Fleets: 3

This indicates that there will be 3 car fleets reaching the destination.