|
навскидку тут всё просто: сортируем отрезки по левому краю. Далее держим приоритетную очередь ордеров (на вершине - тот ордер, у которого левее других правый край последнего отрезка). Обходим отсортированный массив, берем из него очередной отрезок. Если у этого отрезка левый край вписывается в ордер из вершины очереди, то добавляем в этот ордер, просеиваем ордер вниз. Если не вписывается, создаем новый ордер, добавляем в него отрезок, ордер добавляем в очередь. Время работы O(N ln(N)).
Осталось закодить)
|