Последовательная пересекаются два набора интервалов

Question

У нас есть два набора интервалов, A и B.

Каждый выдерживая интервал в А описывается двумя положительными действительными числами {A1start,A1end},{A2start,A2end},...,{Anstart,Anend}. Anend alsways>Anstart. Интервалы в A MAY перекрываются.

Набор B определяется только двумя значениями: длина интервала и расстояние между интервалами. Длина интервала - это дельта каждого интервала, то есть Bnend - Bnstart, и составляет> 0. Интервальное расстояние - это расстояние между любыми двумя Bnstart. Интервалы в B не могут перекрываться.

Мы знаем, что на любом интервале {A1start,Anend} количество интервалов в A и B ДОЛЖНО быть равным.

Вопрос: на интервале {A1start,Anend} можно ли пересечь B с помощью A последовательно? то есть B1 должен пересекаться A1, B2 должен пересекать A2 и т. д. Это нормально, если какой-либо B пересекает любой другой A, кроме его обозначенного.

Я разработал два правила алгоритма и в настоящее время застрял:

1. правила B позволяют вычислить минимальное и максимальное число интервалов на любом {A1start,Anend}, мы используем его, чтобы отбросить случаи, когда число интервалов в A и B неравноправна.
2. Если какой-либо разрыв в А больше, чем расстояние B, отбросить этот случай, так как по крайней мере, один B не пересекается ни с A.

Какие условия должны быть выполнены для этих двух наборов пересекаются последовательно?

Answer 1

Вы можете решить, как это:

• Разбавить все интервалы А от интервала длины B путем вычитания длины из всех Anstart значений. Вы можете думать о A как о том, как теперь определять все допустимые позиции, где может начинаться интервал в B.
• Проблема в том, можете ли вы пересечь серию точек (B), расположенных на некотором расстоянии друг от друга с интервалом (A). Вы можете решить это, пересекая A1 с A2 смещением на -distance, A3 смещено -2distance ... An смещено -(n-1)distance. Если пересечение всех этих интервалов непусто, то возможно пересечение A и B.