Minimum Platforms

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

Сортировка двух массивов требует O(n log n) , а последующий проход — O(n) , поэтому основную часть затрат составляют сортировки. Отсортированные копии занимают дополнительное пространство O(n) .

Q: Чем задача о минимальном количестве платформ отличается от задачи Meeting Rooms II?

Обе задачи спрашивают о наибольшем количестве интервалов, которые пересекаются в один момент. Здесь поезд занимает платформу вплоть до минуты отправления; в задаче «Meeting Rooms II» комната свободна в тот самый момент, когда заканчивается встреча. При просмотре событий это различие сводится к одному сравнению: при совпадении времени здесь сначала обрабатывается прибытие, а там — окончание встречи.

Q: Можно ли решить задачу о минимальном количестве платформ без сортировки?

Да, поскольку каждое время укладывается в фиксированные показания часов. Создайте 2401 счётчик с индексами, соответствующими числам формата HHMM , добавляйте 1 при каждом прибытии и вычитайте 1 в точке departure + 1 . Максимальная накопленная сумма и будет ответом: время работы O(n + 2400) . Индексы, такие как 1260–1299, не являются временем на часах, и на них не приходится прибытие, поэтому они никогда не задают пик.

СреднеСортировка Жадные алгоритмы Два указателя

+10

На станции есть расписание поездов на один день: поезд i прибывает в arrival[i] и отправляется в departure[i]. Время указано числами HHMM — это время на часах без двоеточия, поэтому 930 означает 09:30.

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

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

Функция

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: время прибытия каждого поезда в виде числа HHMM
departureinteger-array: время отправления каждого поезда в виде числа HHMM; departure[i] соответствует arrival[i]
Возвращаетinteger: наибольшее количество поездов на станции в одну и ту же минуту, то есть минимальное число необходимых платформ

Ограничения

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Время всегда имеет допустимый формат HHMM: его последние две цифры не превышают 59.
Все поезда отправляются в один и тот же день. Массивы не отсортированы.

Примеры

Ввод: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Вывод: 3
Пояснение: В 15:30 на станции стоят три поезда: с 15:00 до 16:00, с 15:20 до 15:35 и с 15:30 до 15:45. Ни в одну минуту их не четыре, поэтому достаточно 3 платформ.

Ввод: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Вывод: 2
Пояснение: Поезд, прибывающий в 12:30, встречается с поездом, отправляющимся в 12:30, и то же самое происходит в 13:00. В каждую из этих минут на станции находятся два поезда, поэтому ответ — 2, а не 1.

Ввод: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Вывод: 2
Пояснение: Поезд с 06:00 до 22:00 занимает одну платформу весь день. Поезда с 07:00 до 07:15 и с 13:00 до 14:00 никогда не встречаются, поэтому они используют вторую платформу: 2.

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

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

Решение

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

Посчитай поезда для каждого прибытия

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

Идея

Поездам, стоящим в одну и ту же минуту, нужны разные платформы, поэтому самая загруженная минута задаёт нижнюю границу. Этого также достаточно: открывай новую платформу только тогда, когда прибывающий поезд обнаруживает, что все открытые платформы заняты. В эту минуту на каждой открытой платформе стоит поезд, а на новой — ещё один, поэтому ты никогда не откроешь больше платформ, чем требуется в пиковый момент.

Количество поездов на станции увеличивается только при прибытии поезда, поэтому самой загруженной будет минута прибытия какого-либо поезда. Для каждого поезда i подсчитай поезда j, для которых arrival[j] ≤ arrival[i] ≤ departure[j]. В обоих сравнениях используется ≤, потому что поезд всё ещё стоит на платформе в минуту отправления.

Каждый из n поездов проверяет все n поездов, поэтому сложность составляет O(n²): 25 миллионов проверок пар для 5000 поездов.

Алгоритм

Установи most = 0.
Для каждого поезда i посчитай поезда j, для которых выполняется условие arrival[j] ≤ arrival[i] ≤ departure[j].
Если это количество больше most, сохрани его.
Верни most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Отсортируйте оба списка и выполните проход с двумя указателями

Идея

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

При совпадении времени прибытие учитывается первым, потому что уезжающий поезд всё ещё занимает платформу в эту минуту. В первом примере после отправления в 1100 количество снова становится равным 0, затем прибытия в 1500, 1520 и 1530 происходят до отправления в 1535, поэтому количество достигает 3.

Когда времена прибытия заканчиваются, оставшиеся отправления могут только уменьшать количество, поэтому обход на этом останавливается. Сортировка занимает O(n log n), а обход — не более 2n шагов.

Алгоритм

Отсортируй копию arrival и копию departure.
Установи для platforms, most, i и j значение 0.
Пока i < n: если arrivals[i] ≤ departures[j], прибавь 1 к platforms, обнови most и увеличь i.
Иначе вычти 1 из platforms и увеличь j.
Верни most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

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

Сравнение с < там, где для включения границы нужно ≤. Во втором примере каждый прибывающий поезд занимает платформу поезда, который уезжает в ту же минуту, и ответ уменьшается с 2 до 1.
Вычитание чисел HHMM: 1300 минус 1259 равно 41, хотя между этими моментами времени одна минута. Сравнивать их безопасно, и решение выполняет только сравнение.
Сортировка поездов по времени прибытия и сравнение каждого поезда только с поездом перед ним. Длительная стоянка, например с 06:00 до 22:00 в третьем примере, пересекается с поездами, расположенными намного дальше в списке.
Пропуск поездов, которые прибывают и уезжают в одну и ту же минуту. Четырём поездам, каждый из которых стоит с 10:00 до 10:00, нужны четыре платформы.

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

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

Сортировка двух массивов требует O(n log n), а последующий проход — O(n), поэтому основную часть затрат составляют сортировки. Отсортированные копии занимают дополнительное пространство O(n).

Чем задача о минимальном количестве платформ отличается от задачи Meeting Rooms II?

Обе задачи спрашивают о наибольшем количестве интервалов, которые пересекаются в один момент. Здесь поезд занимает платформу вплоть до минуты отправления; в задаче «Meeting Rooms II» комната свободна в тот самый момент, когда заканчивается встреча. При просмотре событий это различие сводится к одному сравнению: при совпадении времени здесь сначала обрабатывается прибытие, а там — окончание встречи.

Можно ли решить задачу о минимальном количестве платформ без сортировки?

Да, поскольку каждое время укладывается в фиксированные показания часов. Создайте 2401 счётчик с индексами, соответствующими числам формата HHMM, добавляйте 1 при каждом прибытии и вычитайте 1 в точке departure + 1. Максимальная накопленная сумма и будет ответом: время работы O(n + 2400). Индексы, такие как 1260–1299, не являются временем на часах, и на них не приходится прибытие, поэтому они никогда не задают пик.

def minimumPlatforms(arrival, departure):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

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