Определите, перекрываются ли две серии диапазонов - PullRequest
Новая
       13

Определите, перекрываются ли две серии диапазонов

0 голосов
/ 01 мая 2020

Мой вопрос очень похож на это , однако это не одно и то же.

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

Вот пример того, что я ищу:

У меня есть две серии диапазонов, определяемых следующими параметрами:

Ряд диапазона 1: 

RangeStart: 10
RangeEnd: 20
RepeatEvery: 50
RepeatTill: Infinity

Ряд диапазона 2: 

RangeStart: 0
RangeEnd: 5
RepeatEvery: 20
RepeatTill: 100

Ряд выглядит следующим образом: 

Series 1: (10-20), (60-70), (100-110), ..., ...
Series 2: (0-5), (20-25), (40-45), (60-65), (80-85)

1----[XX]------------------------------------[XX]------------------------...
2[]-------------[]-------------[]------------[]-------------[]

Мы можем видеть, что эти конкретные ряд диапазонов перекрывается в диапазоне S1: 60-70, S2: 60-65. Это означает, что алгоритм вернет true.

Что такое быстрый алгоритм, который реализует это?

Я использую c ++

1 Ответ

0 голосов
/ 02 мая 2020

Сначала давайте предположим, что ваши диапазоны никогда не заканчиваются, и найдем первое пересечение.

Совершенно очевидно, что если диапазоны пересекаются, они будут пересекаться в диапазоне [0, lcm(RepeatEvery)].

Теперь это можно использовать технику двух указателей. Мы укажем диапазон в первой серии и второй. Если текущие диапазоны пересекаются - хорошо, мы нашли пересечение. Если они этого не делают, измените диапазон с меньшим началом на следующий. Если новый диапазон начинается после lcm, пересечение отсутствует.

Поскольку lcm <= RepeatEvery1 * RepeatEvery2, этот алгоритм равен O(RepeatEvery1 + RepeatEvery2). Почти наверняка есть более быстрое решение, но это тоже может быть хорошо.

Примечание: под lcm я подразумеваю наименьшее общее кратное

...