PHP Lang
  1. PHP Lang
  3. Интервалы перекрытия и количество перекрытий
Intereting Posts
Magento – получить родительскую категорию и все подкатегории Решение библиотеки PHP Chart Почему это создает черное изображение? Как создать маршрут в symfony 2, который отображает внешний URL? PHP записывает 800 записей в файл (.txt) из базы данных как получить дату для праздников, используя php Yii – удалить 'index' из URL htaccess переписать несколько доменов Обновить статус ответа посетителей – API календаря Google (PHP) Есть ли стандарт и реализация для события Icalendar RSVP Как перенаправить различные запросы поддонов на другой порт Поиск подстановочных файлов vqmod с использованием regex Получать переменные переменные входы от PHP в c ++ Как объединить несколько изображений и текст в одно изображение? Facebook Передача аргументов в файлы JPG и отображение пользовательских изображений

Интервалы перекрытия и количество перекрытий

Этот вопрос может быть похож на других, но немного отличается. Скажем, у нас есть набор интервалов, которые идут, как это, скажем, A-9 – это числа, но ради форматирования я использовал буквы): 

<-a---> <------c---> <------------MAIN> ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 <--d-> <--b------->

Итак, у нас есть главный интервал, идущий от I до Z , интервал a который идет от M к S и т. Д.

Теперь я хочу иметь интервалы, в которых у меня есть большинство совпадений внутри основного (что по существу является основным ограничением), которое будет MO с (a и d) и QS (a и b) и UZ (b и c) с 2 перекрывается каждый (все за пределами Z может быть и речи, потому что оно находится за пределами основного интервала

Мне по существу нужен список (aka array) интервалов и количество перекрытий внутри Main, в то время как не считая основной в это число (сортировка не требуется, есть достаточно способов сделать это) в PHP.

Я подумал сделать снимки интервалов, а затем подсчитать цвета для каждого столбца пикселя, но это

  1. предотвращение проблемы
  2. неэффективный
  3. вероятно, довольно медленно

поэтому, TLDR, мне нужно решение, которое

  • работает в PHP
  • относительно быстро
  • является надежным
  • дает вам перекрывающиеся интервалы с их совпадением
  • имеет основной интервал, используемый в качестве базового ограничения, который не учитывается при перекрытии.

Я знаю, что это очень конкретный вопрос, но я недостаточно разбираюсь в математике и алгоритмах.

  • Постройте 2 вектора. Один содержит начальные точки, а один содержит конечные точки каждого интервала.

  • Сортируйте 2 вектора.

  • Хотя у вас есть что-то в любом из двух векторов:

    • выберите минимум между 2.
    • Если вы выбрали его из вектора с начальными точками, увеличьте количество перекрывающихся интервалов на 1, иначе уменьшите его на 1.
    • Если ваша точка также является отправной точкой основного интервала, установите флаг, который теперь будет действительным.
    • Если ваша точка является конечной точкой основного интервала, вы можете остановиться.
    • Если флаг установлен, вы можете сравнить текущее количество перекрывающихся интервалов с максимальным до сих пор и соответствующим образом обновить.

Вы можете уменьшить 1 от максимума, чтобы игнорировать основной интервал. Вы можете сохранить список разделов, где у вас есть максимальное количество (просто убедитесь, что вы очистите его, когда получите лучший результат).

Это O (NlogN) с количеством интервалов, которые у вас есть.

Основной алгоритм для этого – по всей длине с счетчиком, который увеличивается, когда вы встречаете начальную точку и уменьшается, когда вы встречаете конечную точку.

Следите за максимальным значением, которое получает этот счетчик.

Перейдите по всей длине снова, на этот раз добавьте места в массив result когда:
1. Вы находитесь в пределах основных границ.
2. Ваш счетчик (который поддерживается таким же образом) равен максимальному вы рассчитанному ранее.