Почему алгоритм скользящего окна не работает для этой постановки задачи?
Вопрос в алгоритме, который я использую для решения проблемы. Постановка задачи: (или посмотрите здесь)
«Дано время прибытия и отправления всех поездов, прибывающих на железнодорожную станцию. Найти минимальное количество платформ, необходимых для железнодорожной станции, чтобы ни один поезд не заставлялся ждать. Учтите, что все поезда прибывают в один и тот же день и отправляются в один и тот же день. Время прибытия и отправления поезда никогда не может быть одинаковым, но мы можем сделать так, чтобы время прибытия одного поезда было равно времени отправления другого. В любой момент времени одна и та же платформа не может использоваться как для отправления поезда, так и для прибытия другого поезда. В таких случаях нам нужны разные платформы».
Пример:
Input: n = 6, arr[] = {0900, 0940, 0950, 1100, 1500, 1800},
dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation: There are three trains during the time 0940 to 1200. So we need minimum 3 platforms.
Я пытаюсь использовать следующий алгоритм: Я создаю массив, состоящий из прибытия и отправления каждого поезда. время (так что для приведенного выше тестового примера что-то вроде: [[0900,0910], [0904, 1200], ...] ) Затем я сортирую его по времени прибытия, и если два поезда прибыли одинаково, они сортируются по времени отправления (в порядке возрастания для обоих).
По сути, я пытаюсь найти максимальное количество пересекающихся интервалов. Рассмотрим первый интервал: у него время прибытия «a», время отправления «b». Теперь для любых последующих интервалов, если он прибывает до «b», мне потребуется дополнительная платформа для этого поезда (поскольку он пересекается с первым интервалом). Я продолжаю делать это и нахожу больше интервалов, пока не достигну интервала, время прибытия которого больше, чем «b». На этом этапе первый интервал больше не действителен, поскольку этот поезд уже ушел, поэтому я увеличиваю свой первый указатель, и этот процесс повторяется. В любой точке итерации все интервалы между моими указателями «i» и «j» будут пересекаться. Наконец, в качестве ответа я возвращаю максимальное количество пересекающихся интервалов.
Этот алгоритм работает для первых нескольких тестовых случаев, но по какой-то причине он не работает для некоторых других тестовых случаев.
Код ниже — это то, что я написал для этого алгоритма. Вы можете попытаться отправить его по ссылке выше, чтобы получить неправильный тестовый пример (он довольно большой, поэтому я не думаю, что мне следует вставлять его сюда. Но если вы хотите, я могу вставить неверный тестовый пример в комментариях).
Код С++
class Solution{
public:
//Function to find the minimum number of platforms required at the
//railway station such that no train waits.
static bool comp(pair<int,int>&p1, pair<int,int>&p2) {
if (p1.first == p2.first) return p1.second < p2.second;
return p1.first < p2.first;
}
int findPlatform(int arr[], int dep[], int n)
{
int i = 0, j = 0;
int mxi = 0;
vector<pair<int,int>>mp;
for (int k = 0; k<n; k++) {
mp.push_back({arr[k], dep[k]});
}
sort(mp.begin(), mp.end());
while (j < n) {
while (mp[j].first > mp[i].second) {
i++;
}
mxi = max(mxi, j-i+1);
j++;
}
return mxi;
}
};
Я не прошу правильного алгоритма (так как я его уже прочитал и понял). Я просто хочу знать, почему это неверно, и для какого небольшого тестового примера это не удастся, или я упускаю какой-либо другой случай.
ПС. Я не уверен, что стоит задавать конкретную проблему, связанную с переполнением стека, но я не смог найти другого подходящего веб-сайта/форума, где я мог бы получить быстрый и надежный ответ.
Спасибо!
Да. Я запустил его через отладчик и не заметил неожиданного поведения. Фактически, код проходит приведенные примеры тестовых примеров и некоторые другие, но позже терпит неудачу. Я не уверен, что это неправильная логика, или в моем коде отсутствует какой-либо другой случай.
Я пропустил его через отладчик и не заметил неожиданного поведения. В задачи отладчика не входит наблюдение неожиданного поведения. Ваша задача — наблюдать за неожиданным поведением. Отладчик понятия не имеет, что должна делать ваша программа, это знаете только вы. Отладчик позволяет вам запускать вашу программу по одному шагу, наблюдать за переменными, видеть ход выполнения программы, а затем вы решаете, где и когда программа пойдет по пути, отличному от ожидаемого.
Примечание: не ждите здесь быстрых ответов. Вы получаете то, что получаете.
Кроме того, этот сайт «гиков» известен неверной информацией и неправильным программированием на C++. Наконец, при использовании std::pair<int,int> нет необходимости в специальной функции сравнения для std::sort. У std::pair есть перегруженный <, который выполняет сравнение.
Примечание: старайтесь избегать i и j, за исключением случаев, когда они соответствуют переменным, указанным в литературе, описывающей алгоритм. Иногда мне кажется, что я заплатил большую часть своих ипотечных споттингов, когда другие программисты скрещивали свои визуально похожие переменные. Возможно, вы не пересекли их здесь (а может, и пересекли, и даже я этого не заметил), но рано или поздно вы это сделаете.
Если вы застряли в поиске сломанного набора входных данных, попробуйте создать его с помощью фаззинга. Обратите внимание, что вы не можете выбирать полностью случайные числа, поскольку ни один поезд не может иметь одинаковое время прибытия и отправления, и, предположительно, ни один поезд не может уйти до прибытия. Если вы нашли сломанный набор, постарайтесь уменьшить его. В процессе вы узнаете много нового о проблеме, возможно, достаточно, чтобы самостоятельно ответить на вопрос. Но если нет, добавление набора входных данных и небольшой функции main, которая его вводит, сделает проблему намного более привлекательной для потенциальных ответчиков.
Также знайте, что судья будет полным ублюдком, изо всех сил старающимся вас подставить. Когда вы придумываете тестовые входные данные, вам нужно быть таким же ублюдком. Изо всех сил старайтесь сломать программу. Будьте беспощадны.
Интересное примечание: 0000 ≤ arr[i] ≤ dep[i] ≤ 2359, а время прибытия и отправления никогда не может быть одинаковым, поскольку поезд кажется несовпадающим. arr[i] ≤ dep[i] подразумевает, что прибытие может равняться отбытию.
Поскольку похоже, что у вас есть ввод, при котором ваша программа дает сбой, что вы узнали, запуская отладчик с этим вводом?
Использование отладчика не поможет вам, если вы не сможете определить соответствующие тестовые примеры, ожидаемые выходные данные этих тестовых примеров и (в случае возникновения сбоев) сравнить их с полученными результатами. Для неудачных тестовых случаев вам необходимо посредством анализа определить, какие промежуточные результаты ожидаются. Затем вы сможете использовать отладчик (проходя по коду, реализующему алгоритм), чтобы определить, где поведение кода отличается от ваших ожиданий.
@PaulMcKenzie Извините, если я недостаточно ясно выразился, но я имел в виду следующее: я запустил его через отладчик, но не заметил ничего, что приводило бы к сбою в коде тестового примера. В неудачном тестовом примере было более 800 значений времени прибытия и отправления по отдельности, поэтому я смог проанализировать только несколько начальных.
Часто отладчик мало чем может помочь без малейших ошибок, приводящих к сбою.
Ответы 1
Неправильно учитывать интервал движения только одного поезда за раз. Рассмотрим следующие 3 поезда:
arrivals = [ 0, 100, 300]
departures = [500, 200, 400]
Временное окно, в течение которого первый поезд находится на платформе, полностью покрывает временное окно оставшихся двух поездов, но второй поезд уходит до прибытия третьего поезда, поэтому его платформу можно использовать повторно. Следовательно, всего необходимы только 2 платформы, но ваш код выводит 3.
Правильное решение — это просто стандартная сортировка времени и последующий учет текущего количества поездов, находящихся на платформе. Поскольку в задаче указано, что 0 <= arr[i] <= dep[i] <= 2359, на самом деле ее можно решить за линейное время с помощью метода, похожего на сортировку подсчетом: просто отслеживайте количество поездов, которые прибывают и отправляются в каждый момент времени.
int findPlatform(int arr[], int dep[], int n) {
const int MAX_TIME = 2359;
std::unordered_map<int, int> incomingTrains;
for (int i = 0; i < n; ++i) ++incomingTrains[arr[i]], --incomingTrains[dep[i] + 1];
int minStations = 0, currTrains = 0;
for (int i = 0; i <= MAX_TIME; ++i)
minStations = std::max(minStations, currTrains += incomingTrains[i]);
return minStations;
}
Немного более сложную версию этой проблемы см. в разделе Распределение помещений от CSES. Для этого также требуется вывести назначенную комнату/платформу.
Большое спасибо. Тестовый пример, в котором мой алгоритм не справился, выдавал ответ, превышающий ожидаемый. Вероятно, из-за множества подобных интервалов.
@ BlazeRod11 Рад помочь.
Вы уже просматривали свой код с помощью отладчика?