Пересечение временных промежутков

Главные вкладки

Аватар пользователя dobradmin dobradmin 15 сентября 2009 в 22:48

Парни сам не могу сообразить. Похоже что здесь жесткая математика:(
множество пар время начала - время конца
проверить пересекается ли другая пара время начала - время конца(статичная, не из множества) с каким либо элементом из множества.
все время в timestamp.
не могу алгоритм придумать.

Комментарии

Аватар пользователя VladSavitsky VladSavitsky 15 сентября 2009 в 23:56

Элементарная задача. Я думаю, что стоит просто отдохнуть.
Алгоритм примерно такой:
Диапазон1: начало1 - конец1
Диапазон2: начало2 - конец2

Если начало2 < конец1 И начало2 > начало1 - диапазоны пересекаются
Если при этом конец2 < конец1 И конец2 > начало1 - Диапазон 2 находится внутри Диапазона1.
Иначе - диапазоны просто пересекаются и Диапазон2 начинается после начала Диапазона1.
Вот и вся логика.
Я ещё делал отдельную функцию, которая проверяет равенство диапазонов, чтобы ускорить работу скрипта и не делать лишних вычислений.
Удачи.

Аватар пользователя shefkzn shefkzn 15 сентября 2009 в 23:59

Могу подсказать чисто алгоритмически:
имеем переменные для каждого сравнения
st_beg - начало статической пары
st_end - конец статической пары
din_beg - начало очередной сравниваемой динамической пары из списка
din_end - конец очередной сравниваемой динамической пары из списка
берёшь время окончание статической пары и сравниваешь с временами начала элементов-пар из множества
для каждой пары из множества
st_end < din_beg - значит не пересеклось (ситуация 1)
st_end > din_beg - значит сравниваешь дальше
st_beg и din_end
если st_beg > din_end - значит не пересеклось (ситуация 2)
иначе пересеклось при чём может быть пересечение или вложение одного участка в другой (ситуация 3,4,5,6)

Статическая пара [] динамическая пара ()
ситуация 1: []() st_end < din_beg
ситуация 2: ()[] st_end > din_beg и st_beg > din_end
ситуация 3: ([]) st_end > din_beg и st_beg < din_end
ситуация 4: [()] st_end > din_end и st_beg < din_end
ситуация 5: [(]) st_end > din_beg и st_beg > din_beg
ситуация 6: ([)] st_end > din_end и st_beg < din_beg

За два сравнения оператором IF вы получите сведение о пересечении либо непересечении статической пары и одной динамической пары из списка.
проделав дополнительные сравнения вы получите исчерпывающие сведения о взаимо расположении этих пар
Далее необходимо проделать со всем списком.
Надеюсь понятно объяснил, если чо пиши. Сам я выпускник Мехмата Казанского Гос Университета, так что, как говорится за базар отвечаю))))))

Аватар пользователя shefkzn shefkzn 16 сентября 2009 в 0:01

лучше сравнивать последовательно - в 2 этапа, тогда для некоторых сиьуаций вы съэкономите время и ресурсы вычисления ))) это нас на методах оптимизации расчётов так учили

Аватар пользователя goodboy goodboy 16 сентября 2009 в 11:20

Сортируем пару сравниваемых диапазонов по принципу: у которого дата начала меньше - называем 1-м, остальной 2-м.

Диапазон1: beg1 - end1
Диапазон2: beg2 - end2

Если beg2 > end1 - диапазоны не пересекаются, иначе - пересекаются.