Интервалы перекрытия и количество перекрытий
Этот вопрос может быть похож на другие, но немного отличается. Допустим, у нас есть набор интервалов, который выглядит следующим образом, скажем, A-9 — числа, но для форматирования я использовал буквы):
<-a---> <------c--->
<------------MAIN>
ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789
<--d-> <--b------->
Таким образом, у нас есть основной интервал, который идет от I в Zинтервал a это идет от M в S и так далее.
Теперь я хочу, чтобы интервалы, в которых у меня было наибольшее количество перекрытий, в пределах основного (который по сути является основным ограничением), который был бы МО с (a и d) и QS (a и b) и UZ (b и c) с 2 перекрытия каждый (все за пределами Z не может быть и речи, потому что это вне основного интервала
По сути, я хочу получить список (он же массив) интервалов и количество перекрытий внутри Main, не считая при этом основную часть с этим числом (сортировка не нужна, для этого достаточно способов) в PHP.
Я думал о том, чтобы сделать картину интервалов и затем подсчитать цвета для каждого столбца пикселей, но это
- предотвращение проблемы
- неэффективный
- вероятно, довольно медленно
Итак, TLDR, мне нужно решение, которое
- работает в PHP
- является относительно быстро
- надежный
- дает вам перекрывающиеся интервалы с их количеством перекрытий
- имеет основной интервал, используемый в качестве базового ограничения, который не учитывается в перекрытии.
Я знаю, что это очень специфический вопрос, но я не очень хорошо разбираюсь в математике и алгоритмах.
Решение
-
Построить 2 вектора. Один содержит начальные точки, а другой — конечные точки каждого интервала.
-
Сортировать 2 вектора.
-
Пока у вас есть что-то в любом из двух векторов:
- выберите минимум между 2.
- Если вы выбрали его из вектора с начальными точками, увеличьте число перекрывающихся интервалов на 1, иначе уменьшите его на 1.
- Если ваша точка также является начальной точкой основного интервала, установите флаг, что ваши результаты действительны сейчас.
- Если ваша точка является конечной точкой основного интервала, вы можете остановиться.
- Если флаг установлен, то вы можете сравнить текущее количество перекрывающихся интервалов с максимальным на данный момент и обновлять соответствующим образом.
Вы можете уменьшить 1 от максимума, чтобы игнорировать основной интервал. Вы можете сохранить список разделов, где у вас есть максимальное количество (просто убедитесь, что вы очистите его, когда вы получите лучший результат).
Это O (NlogN) с количеством интервалов, которые у вас есть.
Другие решения
Основной алгоритм для этого — пройти по всей длине со счетчиком, который увеличивается при достижении начальной точки и уменьшается при достижении конечной точки.
Следите за максимумом этого счетчика.
Снова пройдитесь по всей длине, на этот раз добавьте места к вашему result массив когда:
1. Вы находитесь в пределах ОСНОВНОЙ границы.
2. Ваш счетчик (который поддерживается таким же образом) равен максимуму, который вы рассчитали ранее.