Sobreposição entre dois intervalos: raciocínio / algoritmo para encontrar o conjunto de intervalos disjuntos e sobrepostos

Question

Considere os inteiros positivos {1, 2, 3, 4, ...} e a linha de números inteiro correspondente.

Suponha que tenhamos quatro números inteiros, A, B, C e D.

Por exemplo:

_________________ a ___________________________ b __________________ ___________________________ c __________ d _________________________

ou

_________________ a ___________________________ b __________________ ___________________________ c ____________________________ d _______

Considere a notação AB como o conjunto de todos os números consecutivos A, ...., B e o CD do intervalo como o conjunto de todos os números consecutivos C, ..., d.

Eu gostaria de saber uma ressonância simples e generalizada e generalizada (demonstração matemática seria realmente apreciada) que podemos aplicar se quisermos encontrar todos os intervalos consistindo nos números "disjuntos" e dos números "sobrepostos" entre os dois conjuntos de números, ab e CD.

Exemplo 1: se ab= {2, 3, 4, 5, 6, 7, 8, 9} e CD= {4, 5, 6, 7}, temos o seguinte subconjuntos para cada conjunto ab e CD:

• para AB: {2, 3}, {4, 5, 6, 7} e {8, 9}
• para CD: {4, 5, 6, 7}

Exemplo 2: se ab= {2, 3, 4, 5, 6, 7, 8, 9} e CD= {4, 5, 6, 7, 8, 9, 10 , 11, 12}, temos os seguintes subconjuntos para cada conjunto AB e CD:

• para ab: {2, 3}, {4, 5, 6, 7, 8, 9}
• para CD: {4, 5, 6, 7, 8, 9} e {10, 11, 12}

Mas, qual seria um grande e ainda simples raciocínio por trás do desjunto e sobrepostos conjuntos de números entre dois conjuntos de números inteiros?

Muito obrigado por qualquer pista !!

Answer 1

Para dois inteiros $ a $ e $ B $ onde $ A \ le b $ , deixe $ [a, b) $ denotam o intervalo meio aberto meio fechado que consiste nos números < Span Class="Recipiente de Matemática"> $ A, A + 1, \ CDOts, B-1 $ . Em particular, se $ a , então há $ BA $ Números em $ [a, b) $ . Se $ a= b $ , então não há números em $ [a, b) $ . Por exemplo,

• $ [0,1) $ significa o número 0.
• ambos $ [0,0) $ e $ [3, 3) $ significa sem números .
• $ [5,11) $ significa os números $ 5,6,7,8,9,10.
• para denotar os números $ - 2, -1, 0, 1, 2 $ , podemos usar $ [ -2, 3) $ .

---

uma boa propriedade de intervalo meio aberto semestral: se $ l \ le m \ le R $ , então $ [L, R)= [L, M) \ SQCP [M, R) $ .

Prova: Receio que seja óbvio por definição. Feito.

---

Suponha que recebemos $ [a, b) $ e $ [c, d) $ , onde $ a \ lt b $ e $ c \ lt d $ . Em seguida, $ [a, b) $ sobreposs $ [c, d) $ se e apenas $ \ max (A, C) \ lt \ min (B, d) $ .

Prova:

" $ \ rightarrow $ ": Deixe $ n $ ser um número em ambas as $ [a, b) $ e $ [c, d) $ , ou seja, $ a \ le n \ lt b $ e $ c \ le n \ lt d $ . Então $ \ max (a, c) \ le n \ lt \ min (b, d) $ .

" $ \ lentow $ ": $ a \ le \ max (a, c) \ lt \ min ( B, d) \ Le B $ , isto é, $ \ max (A, c) \ in [a, b) $ . Da mesma forma, $ \ max (A, C) \ em [c, d) $ . Então $ [a, b) $ sobreposs $ [c, d) $ .

feito.

---

suponha $ [a, c) $ e $ [b, d) $ sobreposição. Então nós temos as seguintes decomposições definidas.

• $ [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) $

Prova:

Temos $ a \ le \ max (a, c) \ le \ le b $ . Então,

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

---

Exemplo 1: se $ i={2, 3, 4, 5, 6, 7, 8, 9} $ e $ J={4, 5, 6, 7 \} $ , então $ i= [2,10 ) $ e $ j= [4,8) $ . Nós temos as seguintes decomposições definidas.

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

exemplo 2: se $ i= {2, 3, 4, 5, 6, 7, 8, 9} $ e $ J= {4, 5, 6, 7, 8, 9, 10, 11, 12} $ , então $ I= [2,10) $ e $ j= [4,13) $ . Nós temos as seguintes decomposições definidas.

• $ [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) $ .

Os exemplos acima devem indicar claramente o algoritmo que decompõe dois intervalos sobrepostos em intervalos disjuntos.