Существует решение во времени O (n log n), где n - количество заданных временных пар.Вы должны ответить на вопрос: сколько поездов стоит на станции одновременно?Для этого сначала «нормализуем» значения времени: определите все временные сегменты, в которых может произойти что-то интересное. Для этого рассортируйте все данные о времени прибытия и отправления и исключите дубликаты.
В вашем примере с T ={[1,5], [2,4], [5,9], [3,10]}, в результате получается массив A с точками времени [1,2,3,4,5,9,10]и размер m = 7.
Теперь мы переводим время прибытия и отправления каждой пары во временные сегменты, которые поезд занимает на станции, т.е. мы находим индекс значений времени в массиве A (через двоичный файлпоиск).Напримердля [3, 10] мы получаем индексы 2 и 6, считая с нуля.
Вот и все для легкой части.Сортировка и сопоставление значений времени с индексами выполняются в O (n log n) каждый.Теперь для каждого индекса нужно посчитать, сколько поездов стоит на станции в это время.Чтобы сделать это эффективно, мы используем дерево сегментов.
На этом сайте рассказывается, как использовать деревья сегментов: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
Далее вы найдете реализацию на C ++.,Я надеюсь, что вы можете адаптировать его к вашим потребностям.Если какие-либо вопросы остаются открытыми, не стесняйтесь их задавать.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/** Given a number n and n pairs of arrival and departure times of trains,
* this program calculates the number of platforms needed in time O(n log n)
* If a train arrives exactly when another one leaves the station, you need
* two platforms. */
int main () {
int n;
cin >> n;
vector< pair<int,int> > T(n);
vector< int > A(2*n);
for (int i = 0; i < n; ++i) {
int arrival, departure;
cin >> arrival >> departure;
A[2*i] = arrival;
A[2*i+1] = departure;
T[i] = pair<int,int>(arrival, departure);
}
sort(A.begin(), A.end());
int m = unique(A.begin(), A.end()) - A.begin();
// for easy indexing, we need m to be a potency of 2
int pot2m = 1; while (pot2m < m) pot2m *= 2;
// Elements pot2m ... pot2m + m represent the bottom layer of the segment tree
vector< int > segtree(2*pot2m+1, 0);
// Now let's add everything up
for (int i = 0; i < n; ++i) {
int arrival = find(A.begin(), A.end(), T[i].first) - A.begin();
int departure = find(A.begin(), A.end(), T[i].second) - A.begin();
// Now increment
int a = arrival + pot2m;
int b = departure + pot2m + 1;
while (a < b) {
if (a % 2 == 1) ++segtree[a];
if (b % 2 == 1) ++segtree[b-1];
a = (a+1) / 2;
b = b / 2;
}
}
// Find the maximum value in the cells
int a = pot2m;
int b = pot2m + m;
while (a < b) {
int i, j;
for (i = a/2, j = a; j < b-1; ++i, j+=2) {
segtree[i] += max(segtree[j], segtree[j+1]);
}
if (j == b-1) segtree[i] += segtree[j]; // To handle odd borders
a /= 2;
b /= 2;
}
cout << "You need " << segtree[1] << " platforms." << endl;
return 0;
}