Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

853. Car Fleet

Time: $O(n\log n)$

Space: $O(n)$

			


struct Car {
  int pos;
  double time;  // Time to reach the target
};

class Solution {
 public:
  int carFleet(int target, vector<int>& position, vector<int>& speed) {
    int ans = 0;
    vector<Car> cars(position.size());

    for (int i = 0; i < position.size(); ++i)
      cars[i] = {position[i], (double)(target - position[i]) / speed[i]};

    sort(begin(cars), end(cars),
         [](const auto& a, const auto& b) { return a.pos > b.pos; });

    double maxTime = 0;  // The time of the slowest car to reach the target

    for (const Car& car : cars)
      // A car needs more time to reach the target, so it becomes slowest
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
};




			


class Car {
  public int pos;
  public double time;

  public Car(int pos, double time) {
    this.pos = pos;
    this.time = time;
  }
}

class Solution {
  public int carFleet(int target, int[] position, int[] speed) {
    int ans = 0;
    Car[] cars = new Car[position.length];

    for (int i = 0; i < position.length; ++i)
      cars[i] = new Car(position[i], (double) (target - position[i]) / speed[i]);

    Arrays.sort(cars, (a, b) -> b.pos - a.pos);

    double maxTime = 0; // The time of the slowest car to reach the target

    for (Car car : cars)
      // A car needs more time to reach the target, so it becomes slowest
      if (car.time > maxTime) {
        maxTime = car.time;
        ++ans;
      }

    return ans;
  }
}




			


class Solution:
  def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
    ans = 0
    times = [
        float(target - p) / s for p, s in sorted(zip(position, speed),
                                                 reverse=True)]
    maxTime = 0  # The time of the slowest car to reach the target

    for time in times:
      # A car needs more time to reach the target, so it becomes slowest
      if time > maxTime:
        maxTime = time
        ans += 1

    return ans