Überlappung zwischen zwei Intervallen: Begründung / Algorithmus, um den Satz von disjunktischen und überlappenden Intervallen zu finden

Question

Betrachten Sie die positiven Ganzzahlen {1, 2, 3, 4, ...} und die entsprechende Zahlenzahlenzeile.

Angenommen, wir haben vier Integer-Zahlen, A, B, C und D.

Beispiel:

_________________ a ___________________________ b __________________ ___________________________ c __________ d _________________________

oder

_________________ a ___________________________ b __________________ ___________________________ c ____________________________ d _______

Betrachten Sie die Notation AB als Set aller aufeinanderfolgenden Zahlen A, ..., B und der Intervall-CD als Set aller aufeinanderfolgenden Zahlen C, ..., d.

Ich würde gerne eine einfache, aber abstrakte und allgemeinalisierte Resoning wissen (mathematische Demonstration wäre wirklich atemberaubend), dass wir sich anwenden können, wenn wir alle Intervalle finden, die aus den "disjunkten" Zahlen und den "überlappenden" Zahlen zwischen beiden Set besteht von Zahlen, AB und CD.

Beispiel 1: wenn ab= {2, 3, 4, 5, 6, 7, 8, 9} und cd= {4, 5, 6, 7}, wir haben folgendes Subsets für jedes Set AB und CD:

• für AB: {2, 3}, {4, 5, 6, 7} und {8, 9}
• für CD: {4, 5, 6, 7}

Beispiel 2: wenn ab= {2, 3, 4, 5, 6, 7, 8, 9} und cd= {4, 5, 6, 7, 8, 9, 10 , 11, 12}, wir haben die folgenden Untergruppen für jedes Set AB und CD:

• für AB: {2, 3}, {4, 5, 6, 7, 8, 9}
• für CD: {4, 5, 6, 7, 8, 9} und {10, 11, 12}

aber, welches wäre ein großartiger und doch einfacher Abhängigkeit von disjunktischen und überlappenden Nummernsätzen zwischen zwei gegebenen Set von ganzzahligen Zahlen?

Vielen Dank für jeden Hinweis !!

Answer 1

für zwei Ganzzahlen $ A $ und $ B $ wo $ A \ le b $ , let $ [a, b) $ das halb geschlossene halböffnete Intervall, das aus den Zahlen besteht < Span-Klasse="Math-Container"> $ A, A + 1, \ CDOTs, B-1 $ . Wenn insbesondere $ A , dann gibt es $ BA $ Nummern in $ [a, b) $ . Wenn $ A= B $ , dann gibt es keine Zahlen in $ [a, b) $ . Zum Beispiel

• $ [0,1) $ bedeutet die Nummer 0.
• beide $ [0,0) $ und $ [3, 3) $ bedeutet keine Zahlen .
• $ [5,11) $ bedeutet die Zahlen 5,6,7,8,9,10 $. $
• Um die Zahlen zu bezeichnen $ - 2, -1, 0, 1, 2 $ , können wir $ [ -2, 3) $ .

---

ein schönes Eigentum mit halb geschlossenem halböffentlichen Intervall: wenn $ l \ le m \ le r $ , dann $ [l, r)= [l, m) \ sqcup [m, r) $ .

Beweis: Ich fürchte, es ist offensichtlich, dass es per Definition offensichtlich ist. Fertig.

---

Angenommen, wir erhalten $ [a, b) $ und $ [c, d) $ , wobei $ A \ lt B $ und $ c \ lt D $ . Dann $ [a, b) $ Überschneidungen $ [c, d) $ , falls und nur $ \ max (a, c) \ lt \ min (b, d) $ .

Beweis:

" $ \ Righarrow $ ": Lassen Sie $ N $ eine Zahl in beiden $ [a, b) $ und $ [c, d) $ , dh, dh $ a \ le n \ lt B $ und $ c \ le n \ lt d $ . Dann $ \ max (a, c) \ le n \ lt \ min (b, d) $ .

" $ \ lippeApprow $ ": $ a \ le \ max (a, c) \ lt \ min ( B, d) \ le b $ , dh $ \ max (a, c) \ in [a, b) $ . Ebenso, $ \ max (a, c) \ in [c, d) $ . So $ [a, b) $ Überschneidungen $ [c, d) $ .

fertig.

---

Angenommen, $ [A, C) $ und $ [b, d) $ Überlappung. Dann haben wir folgende Set-Zersetzungen.

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

Beweis:

wir haben $ a \ le \ max (a, c) \ le \ min (b, d) \ le b $ . Also,

$$ \ beginnen {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 {richten} $$

---

Beispiel 1: wenn $ i= {2, 3, 4, 5, 6, 7, 8, 9 \} $ und $ j={4, 5, 6, 7 \} $ , dann $ i= [2,10 ) $ und $ j= [4,8) $ . Wir haben folgende Set-Zersetzungen.

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

Beispiel 2: wenn $ i= {2, 3, 4, 5, 6, 7, 8, 9} $ und $ j= {4, 5, 6, 7, 8, 9, 10, 11, 12} $ , dann $ I= [2,10) $ und $ j= [4,13) $ . Wir haben folgende Set-Zersetzungen.

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

Die obigen Beispiele sollten den Algorithmus deutlich genug angeben, der zwei überlappende Intervalle in disjunkte Intervalle zersetzt.