Car Fleet

Q: Какова временная сложность задачи Car Fleet?

Сортировка по позиции занимает O(n log n) , а проход со стеком — O(n) , поэтому общая временная сложность составляет O(n log n) , а сложность по памяти — O(n) . Проверка каждой машины относительно всех машин впереди неё занимает O(n²) .

Q: Как сравнивать время прибытия без чисел с плавающей точкой?

Время прибытия равно dist / speed . Поскольку скорости положительны, d1 / s1 > d2 / s2 выполняется тогда и только тогда, когда d1 × s2 > d2 × s1 . Обе стороны — целые числа, не превышающие 10^12 , поэтому вычислите их в 64-битном типе, и сравнение будет точным — не нужно учитывать округление.

СреднеСтек Сортировка

+10

Автомобили едут по однополосной дороге к отметке target. Автомобиль i начинает движение с отметки position[i] со скоростью speed[i] миль в час. Обгонять другие автомобили нельзя: догнав более медленный автомобиль, машина остается прямо за ним, и с этого момента они движутся вместе с более низкой скоростью как один караван.

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

Функция

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: миля, к которой направляется каждая машина
positioninteger-array: начальный пробег каждого автомобиля
speedinteger-array: скорость каждого автомобиля в милях в час
Возвращаетinteger: количество флотов, достигших пункта назначения

Ограничения

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Все позиции различны.

Примеры

Ввод: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Вывод: 2
Пояснение: По отдельности машинам на отметках 17, 14, 8 и 2 миль нужно 3, 2, 3 и 3 часа, поэтому машина на отметке 14 догоняет машину на отметке 17, а две другие догоняют их на отметке 20 миль. Машине на отметке 0 нужно 10 часов, и она прибывает одна.

Ввод: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Вывод: 3
Пояснение: Автомобилям на отметках 7, 4 и 0 миль требуется 2/3, 5/2 и 9 часов. Каждый прибудет позже автомобиля впереди, поэтому никто никого не догонит: 3 группы.

Дополнительный вопрос

Позиции — это целые числа меньше target. Сможешь подсчитать количество автопарков за O(n + target) времени, не используя сортировку сравнением?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

На одной полосе машины никогда не меняют порядок, и всё решает то, когда каждая машина прибыла бы в одиночку: (target - position[i]) / speed[i]. Рассматривай машины, начиная с ближайшей к пункту назначения и двигаясь назад. Машина образует новый автопарк только тогда, когда прибыла бы строго позже автопарка впереди неё.

Проверьте каждую машину впереди

Верно, но не успевает на самых больших тестах

Идея

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

Каждый автомобиль проверяет все n автомобилей: 10^8 проверок для n = 10^4.

Алгоритм

Установите fleets = 0.
Для каждой машины i проверьте все машины j, для которых position[j] > position[i].
Если для некоторой j выполняется (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], машина i догоняет другую: пропустите её.
В противном случае машина i возглавляет автоколонну: увеличьте fleets на 1.
Верните fleets.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

Сортируйте по позиции и выстраивайте флоты в стопку

Идея

Отсортированные по позиции, начиная с ближайших к месту назначения, машины впереди текущей — это именно те, которые уже были рассмотрены и уже входят в караваны. Храните караваны в стеке, каждый представлен расстоянием и скоростью ведущей машины, которые определяют время прибытия каравана.

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

В примере 1 машины расположены в порядке 17, 14, 8, 2 и 0, а расстояние, делённое на скорость, равно 3/1, 6/3, 12/4, 18/6, 20/2. Добавьте (3, 1). Машина на позиции 14 присоединяется, поскольку 6 × 1 > 3 × 3 — это неверно. Машина на позиции 8 прибывает одновременно: 12 × 1 = 3 × 4, и присоединяется; машина на позиции 2 тоже присоединяется. Для машины на позиции 0 выполняется 20 × 1 > 3 × 2: добавьте её.

Алгоритм

Отсортируй индексы автомобилей по позиции в порядке убывания.
Начни с пустого стека автоколонн.
Для каждого автомобиля вычисли dist = target - position[i].
Если стек пуст или dist × topSpeed > topDist × speed[i], добавь (dist, speed[i]) в стек; иначе автомобиль присоединяется к верхней автоколонне.
Верни размер стека.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

Ловушки и крайние случаи

Считать точное совпадение новой автоколонной. Машины на отметках 8 и 2 в примере 1 встречаются с автоколонной на отметке 20 и присоединяются к ней. Добавляйте в стек только если время строго больше.
Переполнение при вычислении перекрёстного произведения. 10^6 × 10^6 = 10^12 не помещается в 32 бита: в Java, C, C++, C# и Rust перед умножением расширяйте значения до 64 бит; в R используйте числа с плавающей точкой.
Сортировка в неправильном порядке. Если начинать с машины, наиболее удалённой от пункта назначения, каждая машина сравнивается с машинами позади неё, которые никогда не смогут её задержать.
Сортировка только по position. Сортируйте индексы или пары (position, speed), чтобы каждая скорость оставалась связанной со своей машиной.

Частые вопросы3

Какова временная сложность задачи Car Fleet?

Сортировка по позиции занимает O(n log n), а проход со стеком — O(n), поэтому общая временная сложность составляет O(n log n), а сложность по памяти — O(n). Проверка каждой машины относительно всех машин впереди неё занимает O(n²).

Почему в Car Fleet используется стек?

При просмотре автомобилей спереди каждый новый автомобиль нужно сравнивать только с автопарком непосредственно впереди — с тем, который сформировался последним. Стек удерживает этот автопарк наверху. Поскольку читается только верхний элемент, подойдут и две переменные; кроме того, стек сохраняет сами автопарки.

Как сравнивать время прибытия без чисел с плавающей точкой?

Время прибытия равно dist / speed. Поскольку скорости положительны, d1 / s1 > d2 / s2 выполняется тогда и только тогда, когда d1 × s2 > d2 × s1. Обе стороны — целые числа, не превышающие 10^12, поэтому вычислите их в 64-битном типе, и сравнение будет точным — не нужно учитывать округление.

def carFleet(target, position, speed):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

Ожидаемый вывод