помогите решить задачу

[Alex26RusLink]

Люди помогите плиз решить задачку либо на C++ либо на Паскале. Задача вроде не сложная, то ко длинная, но в голову что-то не лезет.

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).
Дано расписание движения электричек, в котором для каждой электрички указано время её прибытия, а также время отправления в следующий рейс. Электрички в расписании упорядочены по времени прибытия. Поскольку вокзал - конечная станция, то электричка может стоять на нём довольно долго, в частности, электричка, которая прибывает раньше другой, отправляться обратно может значительно поздней.
Тупики пронумерованы числами от 1 до К. Когда электричка прибывает, её ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени Х, то электричку, которая прибывает в момент времени Х, в этот тупик ставить нельзя, а электричку, прибывающую в момент Х+1 - можно.
Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Формат входных данных
Во входном файле число К - количество тупиков и число N - количество электропоездов (1<=K<=500000, 1<=N<=500000). Далее идёт N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задаётся натуральным числом, не превышающим 109. Никакие две электрички не прибывают в одно и то же время. Также возможно, что какая-нибудь электричка(или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички Время отправления каждой электрички строго больше времени её прибытия. Все электрички упорядочены по времени прибытия. Считается что в нулевой момент времени все тупики на вокзале свободны.

Формат выходных данных
В выходной файл выведите N чисел - по одному для каждой электрички: номер тупика, куда прибудет соответствующая электричка. Если тупиков не достаточно, чтобы организовать движение электричек согласно расписанию, в выходной файл должно быть выведено два числа: первое должно равняться 0 (нулю), а второе содержать номер первой из электричек, которая не сможет прибыть на вокзал.

Всё наконец. Если кто-нибудь решит помочь, напишите программу без файлов, плиз...

[Sazary]

Заводите массив тупиков. Заполняете нулями (например), то есть обозначаем, что везде пусто.
Потом заводите двумерный массив событий. В первом столбце - время, во втором - событие. Например, если приходит поезд T, то пишем туда T, а если этот поезд отходит, то пишем -T.
Потом сортируем его.

Далее идем по этому массиву. Если какой-то поезд приходит, то проходим по массиву тупиков и ставим поезд в свободный. Если кто-то отходит, то проходим по массиву в поисках номера поезда и освобождаем тупик.

Пробуйте.

[Alex26RusLink]

мысль понял буду пробовать

[pu4koff]

Я бы сделал так:
Массив тупиков с нулевыми значениями.
Потом приходит некий поезд:
1) Находим первый тупик, в котором значение меньше, чем время прибытия данного поезда
2) Записываем в этот тупик время отбытия данного поезда
В общем как-то так:

int тупик[K]; // массив тупиков
for (int поезд = 0; поезд < N; ++поезд)
{
  т = 0:
  while (тупик[т] >= время_прибытия_поезда_на_вокзал)
  {
    т++;
    if (т >= K)
    {
       // тупиков недостаточно
       return;
    }
  }
  // поезд попадает в тупик т
  тупик[т] = время_отбытия_поезда_с_вокзала;
}

[Alex26RusLink]

мне нравится алгоритм, ток щас опробовать его нада