853-car-fleet

853. Автопарк (Средний уровень) (https://leetcode.com/problems/car-fleet/)

Есть n машин, находящихся на заданном расстоянии от начальной отметки 0 мили, движущихся к отметке target. Вам даны два целочисленных массива position и speed, оба длиной n, где position[i] — начальная миля i-й машины, а speed[i] — скорость i-й машины в милях в час. Машина не может обогнать другую машину, но может её догнать и затем ехать рядом с ней со скоростью более медленной машины. Автопарк — это одна машина или группа машин, едущих рядом друг с другом. Скорость автопарка — это минимальная скорость среди всех машин в этом автопарке. Если машина догоняет автопарк ровно на отметке target, она всё равно считается частью этого автопарка. Верните количество автопарков, которые прибудут к месту назначения. Ограничения: - n position.length speed.length - 1 <= n <= 10^5 - 0 < target <= 10^6 - 0 <= position[i] < target - Все значения position уникальны.

• 0 < speed[i] <= 10

function carFleet(target: number, position: number[], speed: number[]): number {
  let time = 0
  let fleets = 0
  const cars = position.map((p, i) => [p, speed[i]])
  cars.sort((a, b) => b[0] - a[0])
  for (let i = 0; i < cars.length; i++) {
    const currentTime = (target - cars[i][0]) / cars[i][1]
    if (currentTime > time) {
      fleets += 1
      time = currentTime
    }
  }
  return fleets
}
 
// Local check:
console.log(carFleet(12, [10, 8, 0, 5, 3], [2, 4, 1, 1, 3])) // 3
console.log(carFleet(10, [3], [3])) // 1
console.log(carFleet(100, [0, 2, 4], [4, 2, 1])) // 1

Пример 1:
 
    Ввод: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
    Вывод: 3
    Объяснение:
    Машины, начавшие движение с 10 (скорость 2) и 8 (скорость 4), образуют автопарк,
    встречаясь друг с другом на отметке 12. Автопарк формируется на target.
    Машина, начавшая движение с 0 (скорость 1), не догоняет ни одну другую машину, поэтому
    она является автопарком сама по себе.
    Машины, начавшие движение с 5 (скорость 1) и 3 (скорость 3), образуют автопарк,
    встречаясь друг с другом на отметке 6. Автопарк движется со скоростью 1, пока не достигнет
    target.
 
Пример 2:
 
    Ввод: target = 10, position = [3], speed = [3]
    Вывод: 1
    Объяснение: Есть только одна машина, следовательно, есть только один автопарк.
 
Пример 3:
 
    Ввод: target = 100, position = [0,2,4], speed = [4,2,1]
    Вывод: 1
    Объяснение:
    Машины, начавшие движение с 0 (скорость 4) и 2 (скорость 2), образуют автопарк,
    встречаясь друг с другом на отметке 4. Машина, начавшая движение с 4 (скорость 1), доезжает до 5.
    Затем автопарк на отметке 4 (скорость 2) и машина на отметке 5 (скорость 1)
    объединяются в один автопарк, встречаясь друг с другом на отметке 6. Автопарк движется со скоростью 1
    до достижения target.

leetcode