проверить n отрезков (на прямой) на пересечение k из них

Даны n, k и t. Дан массив отрезков (длины n) на прямой, заданный в произвольной форме.

Необходимо найти длину максимального участка пересечения k отрезков.

Вернуть нужно: (значение 1), если таких участков нет, (значение 2), если найденная длина больше t, и (значение 3) в остальных случаях.

При задании массива я могу за очень-очень малое O(1) запросить центр отрезка, и за просто малое O(1) запросить половину его длины.

Мой алгоритм:

отрезки задаю в виде двух массивов lefts и rights длины n каждый - массивы левых и правых концов

сортирую оба массива (MergeSort)

на каждом шаге цикла сравниваю lefts[левый указатель] и rights[правый указатель]

если левый больше, увеличиваю счетчик пересечений и левый указатель

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

если при увеличении счетчика он стал равен k, то найдено начало k-пересечения. запоминаю его
если при уменьшении счетчика он стал равен (k-1), то найден конец k-пересечения. вычисляю длину k-пересечения

в конце цикла смотрю на макс. длину k-пересечения и выдаю ответ.

этот алгоритм работает недостаточно быстро.

Небольшое улучшение: в цикле, если счетчик уже больше k, то после сравнения lefts[левый указатель] и rights[правый указатель] из минимального вычитается запомненное начало k-пересечения. если полученная разность оказывается больше t, то досрочный выход из цикла и возврат (значение 3)

Но даже так алгоритм работает недостаточно быстро.

Подскажите, пожалуйста, в какую сторону копать, чтобы еще уменьшить время работы.

0

Сортируете массив LinePt и просто идете по нему ++ если flagBegin, иначе --

0

Задача решена. Алгоритм прежний, выиграть время удалось в другой части программы.

Сообщение от Igor3D C++ 1 2 3 4 5 struct LinePt {  float x;           // координата начала или конца  bool flagBegin;   // true если это левая точка  CLine * line;   // указатель на линию (если нужно) }; Сортируете массив LinePt и просто идете по нему ++ если flagBegin, иначе --

ваш способ проигрывает моему при сортировке (при сортировке сложностью Knlogn ваш способ дает K*(2n)log(2n) операций, мой - K*2nlogn из-за отдельной сортировки массивов правых и левых точек), а в остальном работает так же. Но все равно спасибо.

Тему можно закрывать

0

Сообщение от trympyrym Задача решена. Алгоритм прежний, выиграть время удалось в другой части программы.

Охотно верю, т.к. в данном фрагменте время практически равно времени сортировки. Экономить на нем - (сортируя 2 массива) мне кажется перегиб, неоправданное усложнение кода. А если уж экономить - сортировать указатели, ведь зависит не только от n*log(n), но и от стоимости операции обмена

0