Флот машин

 Источник: https://leetcode.com/problems/car-fleet/

N машин собираются достичб одной и той же точки назначения на одном и том же маршруте. Точка назначения находится на отметке target миль.

Каждая машина i имеет константную скорость speed[i] (миль/час), и начальную позицию position[i] миль относительно некоторой нулевой точки маршрута к пункту назначения.

Машина не может обойти другую машину, но может присоединиться к ней, продолжая движение бампер за бампером с той же скоростью. В этом случае мы считаем расстояние между машинами равно нулю, и эти машины находятся в одной точке.

Флот машин - это не пустое множество машин, которые движутся вместе (в одних и тех же точках) с одной и той же скоростью. Одна машина - это тоже флот.

Если машина достигает точку назначения одновременно с каким-то флотом, то мы считаем, что она тоже принадлежит этому флоту.

Нужно посчитать, сколько отдельных машинных флотов прибудут в точку назначения.

Пример:

Дано: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Результат: 3
Объяснение:
Машины, стартующие из точек 10 и 8 становятся флотом, поскольку прибывают одновременно в точку назначения 12.
Машина, стартующая из точки 0, не может достичь никакого впереди едущего флота, прибывает самой последней в точку начначения, и считается отдельным флотом.
Машины, стартующие из точек 5 и 3, становятся флотом в точке 6, и достигают точки назначения 12 со скоростью 1.
Итого, количество отдельных флотов, прибывающих в точку назначения 12, равно 3.

Примечания:

1. 0 <= N <= 10 ^ 4
2. 0 < target <= 10 ^ 6
3. 0 < speed[i] <= 10 ^ 6
4. 0 <= position[i] < target
5. Все первоначальные позиции разные.

Идея решения

Назовем "лидирующем флотом" тот флот, перед которым нет никакого другого флота.

Если машина Б едет позади машины А изначально, но могла бы приехать в пунект назначения раньше, чем А, то в какой-то момент Б и А встретятся в одной точке, поэтому они образуют флот и будут ехать со скоростью min(speed[А], speed[Б])=speed[А].

Если скорость Б не позволяет присоединиться к флоту машины А, то А приедет первой в точку назначения, а к Б возможно присоединяться другие машины, едущие позади неё, и образуют с ней флот.

Алгоритм

Зная первоначальную позицию машины и её скорость, мы можем рассчитать время, необходимое для достижения точки назначения по формуле: time = (target - position) / speed. 

Сформируем для каждой машины объект: (position, time), где position - начальная позиция машины. Отсортируем эти объекты по полю position.

Будем просматривать отсортированный массив с конца. Самый последний элемент массива - это машина А. Предпоследний элеемнт массива - машина Б. 

Случай 1. Если Б требуется меньше времени, чем А, чтоб приехать в пункт назначения, значит Б догонит А и они вместе придут в точку назначения единым флотом. Затем мы рассматриваем этот флот, как машину А, а второй с конца элеемнт отсортированного массива - это машина Б. И повторяем наши рассуждения.

Случай 2. Если А требуется меньше времени, чем Б, то Б не может догнать А. Мы увеличиваем счётчик флотов, поскольку А (или флот к нему присоединившийся) достигнет точки назначения отдельно от машины Б и остальных, которые следуют за ней. После чего, машина Б становится машиной А, а машина, следующая за ней, становится машиной Б. И повторяем рассуждения.

Имплементация 

class Solution {
   public int carFleet(int target, int[] pos, int[] speed) {
        int N = pos.length, res = 0;
        double[][] cars = new double[N][2];
        for (int i = 0; i < N; ++i) // формируем объекты(position, time)
            cars[i] = new double[] {pos[i], (double)(target - pos[i]) / speed[i]};
// сортируем объекты по первому полю position ([0])
        Arrays.sort(cars, (a, b) -> Double.compare(a[0], b[0]));
        double cur = 0;
       int ans = 0, t = N;
// начинаем просмотр отсортированного массива с конца
// в поле [1] находится время
        while (--t > 0) {
// t - это машина А, t-1 - это машина Б, случай 2.
            if (cars[t][1] < cars[t-1][1]) ans++;  // увеличиваем счетчик флотов
            else cars[t-1] = cars[t]; // иначе А и Б образуют флот
        }
// если мы до сих пор не увеличили счётчик, то все машины образуют единый флот, поэтому +1
        return ans + (t == 0 ? 1 : 0); //lone car is fleet (if it exists)
    }
}