Перекрытие между двумя интервалами: рассуждение / алгоритм Чтобы найти множество непересекающихся и перекрывающихся интервалов

Question

Рассмотрим положительные целые числа {1, 2, 3, 4, ...} и соответствующая строка целочисленного номера.

Предположим, у нас есть четыре целочисленные номера, A, B, C и D.

Например:

_________________ <Сильные> ___________________________ b __________________ ___________________________ <Сильные> C __________ D _________________________

или

_________________ <Сильные> ___________________________ b __________________ ___________________________ <Сильные> C ____________________________ D _______

Рассмотрим нотацию AB как набор всех последовательных чисел A, ...., B и интервал CD в качестве набора всех последовательных чисел C, ..., d.

Я хотел бы знать простое, но абстрактные и обобщенные резонансы (математическая демонстрация будет действительно предплездана), что мы можем подать заявку, если мы хотим найти все интервалы, состоящие из номеров «непересекающихся» и «перекрывающиеся» чисел между обоими наборами. номеров, ab и cd.

Пример 1: Если ab= {2, 3, 4, 5, 6, 7, 8, 9} и cd= {4, 5, 6, 7} мы имеем следующее Подвеска для каждого набора AB и CD:

.
• для ab: {2, 3}, {4, 5, 6, 7} и {8, 9}
• для CD: {4, 5, 6, 7}

Пример 2: Если ab= {2, 3, 4, 5, 6, 7, 8, 9} и cd= {4, 5, 6, 7, 8, 9, 10 , 11, 12}, у нас есть следующие подведения для каждого набора AB и CD:

.
• для ab: {2, 3}, {4, 5, 6, 7, 8, 9}
• для CD: {4, 5, 6, 7, 8, 9} и {10, 11, 12}

Но какой из них был бы отличным и простым рассуждением за непересекающимися и перекрывающимися наборами чисел между двумя заданными наборами целочисленных чисел?

Большое спасибо за любую подсказку !!

Answer 1

Для двух целых чисел $ a $ и $ b $ где $ [a, b) $ обозначает полузакрытый половина открытого интервала, который состоит из чисел < Spaness Class="Математический контейнер"> $ a, a + 1, \ cdots, b-1 $ . В частности, если $ a , то есть $ ba $ Номера в $ [A, B) $ . Если $ a= b $ , то нет чисел в $ [A, B) $ . Например,

.
• $ [0,1) $ означает номер 0.
• оба $ [0,0) $ и $ [3, 3) $ не имеют значения ,
• $ [5,11) $ означает цифры $ 5,6,7,8,9,10. $
• для обозначения чисел $ - 2, -1, 0, 1, 2 $ , мы можем использовать $ [ -2, 3) $ .

---

Приятное свойство полукодных половинных открытых интервалов: Если $ l \ le m \ le r $ , то $ [L, R)= [L, M) \ SQCUP [M, R) $ .

<Сильное> Доказательство: Боюсь, это очевидно по определению. Сделано.

---

Предположим, нам дают $ [a, b) $ и $ [c, d) $ , где $ a \ lt b $ и $ C \ lt d $ . Затем $ [a, b) $ перекрывает $ [c, d) $ Если и только <класс Span= «Математический контейнер»> $ \ max (a, c) \ lt \ min (b, d) $ .

<Сильное> Доказательство:

" $ \ pruralArrow $ ": Пусть $ n $ Будьте номером в обоих <класс Span= «Математический контейнер»> $ [a, b) $ и $ [c, d) $ , т.е. $ a \ le n \ lt b $ и $ C \ le n \ lt d $ . Затем $ \ max (a, c) \ le n \ lt \ min (b, d) $ .

" $ \ fenderarrow $ ": $ a \ le \ max (a, c) \ lt \ min ( B, d) \ le b $ , т.е. $ \ max (a, c) \ in [a, b) $ . Точно так же $ \ max (a, c) \ in [c, d) $ . Таким образом, $ [A, B) $ Перекрывает $ [c, d) $ .

сделано.

---

Предположим, $ [a, c) $ и $ [b, d) $ перекрывается. Тогда у нас есть следующие множество разложений.

.
• $ [a, b)= [a, \ max (a, c)) \ sqcup [\ max (a, c), \ min (b, d)] \ sqcup [\ min (b, d), b) $
• $ [c, d)= [c, \ max (a, c)) \ sqcup [\ max (a, c), \ min (b, d)] \ sqcup [\ min (b, d), d) $

<Сильное> Доказательство:

У нас есть $ a \ le \ max (a, c) \ le \ min (b, d) \ le b $ . Итак,

$$ \ begin {align} [A, b) &= [a, \ max (a, c)) \ sqcup [\ max (a, c), b) \\ &= [A, \ max (a, c)) \ sqcup [\ max (a, c), \ min (b, d)] \ sqcup [\ min (b, d), b). \ end {align} $$

---

Пример 1: Если $ i={2, 3, 4, 5, 6, 7, 8, 9 \} $ И $ j={4, 5, 6, 7 \} $ , затем $ I= [2,10 ) $ и $ j= [4,8) $ . У нас есть следующие множество разложений.

.
• $ [2,10)= [2, 4) \ SQCUP [4, 8) \ SQCUP [8,10) $ .
• $ [4,8)= [4, 4) \ SQCUP [4, 8) \ SQCUP [8,8)= [4,8) $ ,

Пример 2: Если $ i= {2, 3, 4, 5, 6, 7, 8, 9} $ и $ j= {4, 5, 6, 7, 8, 9, 10, 11, 12} $ , затем $ I= [2,10) $ и $ j= [4,13) $ . У нас есть следующие множество разложений.

.
• $ [2,10)= [2, 4) \ SQCUP [4, 10) \ SQCUP [10,10)= [2, 4) \ SQCUP [4, 10) $ .
• $ [4,13)= [4, 4) \ SQCUP [4, 10) \ SQCUP [10,13)= [4, 10) \ SQCUP [10, 13) $ .

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