Платформы железнодорожной станции

1. Идея

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

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

Следовательно, ответ — это максимальное количество поездов, находящихся на станции одновременно.

Чтобы это посчитать, удобно отдельно отсортировать все времена прибытия и все времена отправления, а затем пройти по ним двумя указателями.

2. Наблюдения

Наблюдение 1

Если следующий по времени момент — это прибытие, то число занятых платформ увеличивается на 1.

Если следующий момент — это отправление, то число занятых платформ уменьшается на 1.

Наблюдение 2

Нас не интересует, какой именно поезд приехал или уехал. Для ответа важно только:

• сколько поездов уже прибыло;
• сколько уже отправилось.

Поэтому можно:

• отсортировать массив arr,
• отсортировать массив dep,
• затем сравнивать текущие минимальные ещё не обработанные времена.

Наблюдение 3

По условию все arr_i и dep_i попарно различны. Это очень удобно: не бывает ситуации, когда поезд прибывает и другой поезд отправляется в один и тот же момент.

Значит, при сравнении arr[i] и dep[j] всегда строго либо одно меньше другого, либо наоборот.

3. Алгоритм

1. Считать n.
2. Считать массив прибытия arr и массив отправления dep.
3. Отсортировать arr.
4. Отсортировать dep.
5. Завести:
   • i — индекс по прибытиям,
   • j — индекс по отправлениям,
   • cur — текущее число занятых платформ,
   • ans — максимальное значение cur.
6. Пока i < n и j < n:
   • если arr[i] < dep[j], то раньше происходит прибытие:
     • увеличить cur,
     • обновить ans,
     • сдвинуть i;
   • иначе раньше происходит отправление:
     • уменьшить cur,
     • сдвинуть j.
7. Вывести ans.

4. Почему это работает

Рассмотрим все события на временной оси: прибытия и отправления.

После сортировки массивов arr и dep указатели i и j всегда показывают на ближайшее ещё не обработанное прибытие и ближайшее ещё не обработанное отправление.

На каждом шаге:

• если arr[i] < dep[j], значит следующее событие — прибытие нового поезда; тогда число занятых платформ увеличивается на 1;
• иначе следующее событие — отправление; тогда одна платформа освобождается, и число занятых платформ уменьшается на 1.

Переменная cur в каждый момент хранит точное число поездов, находящихся на станции после обработки уже просмотренных событий.

Тогда максимальное значение cur за весь процесс и есть максимальное число одновременно занятых платформ. Меньшего числа платформ точно не хватит, потому что в некоторый момент одновременно стояло ans поездов. Большего числа не нужно, потому что ans платформ достаточно для любого момента времени.

Значит, алгоритм действительно находит минимальное необходимое число платформ.

5. Сложность

Сортировка двух массивов занимает O(n log n).

Далее два указателя делают не более 2n шагов, это O(n).

Итоговая сложность: O(n log n).

Дополнительная память: O(1), если не считать сами входные массивы.

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> arr(n), dep(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> dep[i];
    }

    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());

    int i = 0, j = 0;
    int cur = 0, ans = 0;

    while (i < n && j < n) {
        if (arr[i] < dep[j]) {
            cur++;
            if (cur > ans) ans = cur;
            i++;
        } else {
            cur--;
            j++;
        }
    }

    cout << ans << '\n';
    return 0;
}

7. Код на Python 3

n = int(input())
arr = list(map(int, input().split()))
dep = list(map(int, input().split()))

arr.sort()
dep.sort()

i = 0
j = 0
cur = 0
ans = 0

while i < n and j < n:
    if arr[i] < dep[j]:
        cur += 1
        if cur > ans:
            ans = cur
        i += 1
    else:
        cur -= 1
        j += 1

print(ans)