Проблема расчета перекрывающихся диапазонов дат - PullRequest
Новая
       11

Проблема расчета перекрывающихся диапазонов дат

7 голосов
/ 19 сентября 2011

У меня проблема при попытке разработать правильный алгоритм для вычисления набора диапазонов дат.

В основном у меня есть список неупорядоченных диапазонов дат (Список, содержащий массивы времени начала и окончания), и я хочучтобы объединить этот список, чтобы он не содержал перекрывающихся времен.

В основном для объединения двух диапазонов дат: 

if start1 <= end2 and start2 <= end1 //Indicates overlap
   if start2 < start1 //put the smallest time in start1
      start1 = start2
   endif
   if end2 > end1 //put the highest time in end1
      end1 = end2
   endif
endif

Это объединяет два времени дат.

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

Мое функциональное и рекурсивное программирование немного устарело, и любая помощь будет приветствоваться.

Ответы [ 2 ]

15 голосов
/ 19 сентября 2011

Не смотрите на интервалы, смотрите только на их концы.

У вас есть куча начальных моментов и куча конечных моментов.Представьте, что начальные моменты - красные, а конечные - синие.Или представьте, что начальные моменты - это открывающие фигурные скобки, а конечные моменты - закрывающие фигурные скобки.

Поместите их все вместе в список.Сортируйте список от самого раннего к последнему, игнорируя цвет.

Теперь возьмите с собой счетчик, установленный на ноль, и пройдите по списку.Когда вы увидите красный момент, увеличьте счетчик.Когда вы увидите синий момент, уменьшите счетчик.Когда значение счетчика меняется от 0 до 1, выведите «start» и текущее время.Когда значение счетчика изменяется от 1 до 0, выведите «end» и текущее время.Если значение счетчика падает ниже 0, выведите «Хьюстон, у нас проблема».Вы должны закончить со своим счетчиком в 0 и кучей хороших непересекающихся интервалов.

Это старый добрый алгоритм подсчета фигурных скобок.

Иллюстрация. 

 A bunch of overlapping intervals:

 (-------------------) 
                       (----------------------)           
                                                          (---)
       (---------------------)                       
                                                     (-----------------)

 A bunch of interval ends:

 (-----(-------------)-(-----)----------------)      (----(---)--------)
0 голосов
/ 19 сентября 2011
Ответ

n.m. - это все, что вам нужно, но если вы хотите использовать уже созданный код, просто сортируйте диапазоны по времени начала и просматривайте список, объединяя перекрытия.

...