LeetCode - 853. Car Fleet

Thoughts:

Nothing special, only need to use the vanilla sort.

The time complexity will be O(nlogn)

Thoughts visuzlization:

target = 10
position = [1,4]
speed = [3,2]

'+' represents a car
'_' represents an empty place

graph: + _ _ + _ _ _ _ _ _

tips
1. no matter how fast the car is
   it can't pass the next one
   so it'e simpler to iterate calculation from right to left
2. arrived time = (target - position) / speed
   compare the time with the current slowest one
   if the time is slower than the current slowest one
   means it will be a seperate fleet

because I need to sort position and speed by position with decreasing way
so I need to create a array filled pairs like this
paris = [[4,2],[1,3]]
and initialize the current slowest arrived time and car fleet count
slowest = 0
fleetCount = 0

then compare the current arraived time with the current slowest arraived time
if true, it means I found a new car fleet and need to use the current arraived time
to replace the current slowest arraived time

keep looping this
I will get the car fleet count I want

Code:

/**
 * @param {number} target
 * @param {number[]} position
 * @param {number[]} speed
 * @return {number}
 */
var carFleet = function (target, position, speed) {
  const pairs = position.map((p, i) => [p, speed[i]]);
  pairs.sort((a, b) => b[0] - a[0]);
  let maxArrivedTime = 0;
  let fleetCount = 0;
  for (let [p, s] of pairs) {
    const currArrivedTime = (target - p) / s;
    if (currArrivedTime > maxArrivedTime) {
      fleetCount++;
      maxArrivedTime = currArrivedTime;
    }
  }
  return fleetCount;
};

Reference

Original link