Максимальное количество поездов, которые может выдерживать платформа k

Question

Учитывая время прибытия и выезда из N поездов, которые достигают железнодорожного вокзала, для данных платформ k, верните максимальное количество поездов, которые мы можем разместить на платформах k.

k <<< N 

Прибытие и время вылета Массив

Input: arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} 
     dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} 

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

http://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station/ 

Я пробовал жадный алгоритм для этого вопроса, но он не работает для всех тестовых случаев.

Answer 1

Мне кажется (я не строгое доказательство для него), что жадный алгоритм должен работать:

1. Сортировка поездов по времени вылета.

2. Давайте поддерживать массив lastDeparture размера k, где lastDeparture[i] время, когда последний поезд покидает платформу i (первоначально заполненный нулями).

3. Переберем массива поездов и сделайте следующее:

   • Найти все такие платформы, что lastDeparture[i] <= currentTrain.arrival.

   • Если таких платформ нет, продолжайте использовать.

   • В противном случае выберите тот, который имеет наибольшее значение lastDeparture (если таких платформ несколько, мы можем выбрать любой из них).

   • увеличение ответ на один и добавить текущий поезд к этой платформе (то есть назначить lastDeparture[i] = currentTrain.departure

эскиз доказательства:.

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

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

Answer 2

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

Грубая сила:

1. Merge & Сортировать Прибытия и вылеты (но отслеживание, что есть что, и определить, какие прибывает поезд/отходит).
2. Пройдите через массив, добавив один к стойке для каждого прибытия и вычитая по одному для каждого отправления.
3. Если счетчик k и поезд прибывает, отмените поезд, который находится на станции с самым длинным временем слева на платформе во время «переполненного» прибытия. NB: Это может быть прибывающий поезд или поезд уже на платформе.
4. Ответ - общее количество поездов минус количество отмененных поездов.

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

Это будет сложность O (N * K) в худшем случае, если данные о прибытии и отправлении отсортированы и могут быть быстро скреплены друг с другом. Я заметил, что данный пример почти таков.

Сложность - наихудший случай сортировки и O (N * K) подсчет.

Answer 3

Если я правильно понимаю проблему, я считаю, что это можно сделать, используя stack размера k, который будет содержать поезда в настоящее время на платформе. Для каждого поезда (в отсортированном порядке по времени вылета):

while current.ArrivalTime > stack.Last.DepartureTime: 
    remove the top element (train) from the stack 
push the current train IF there is room, else ignore it 
answer = max(answer, stack.Size) 

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

Это должно быть O(n log n) из-за сортировки, так как каждый поезд входит/выходит из стека не более одного раза.