Algorithmus zur Berechnung einer Vereinigungsmenge

[Der Martin]

Hallo,

Ich bilde eine Schnittmengenmatrix

wie machst du das? Und wieso hilft dir das, wo du doch die Vereinigungsmenge (aka Obermenge) haben möchtest?

• a b c d
  a 1 0 0 1
  b 0 1 1 0
  c 0 1 1 0
  d 1 0 0 1
  Jetzt sehe ich das Intervall 'a' mit 'd' eine Vereinigungsmenge bilden und 'b' mit 'c'.

Ich kann dir nicht folgen.

Also kann ich doch sagen das a mit d vereint, ein zusammenhängendes Intervall bilden (b mit d ebenso). Oder bin ich jetzt völlig aufem Holzweg?

Ich glaube ja, bin mir aber nicht sicher.
Lass es mich anders illustrieren. Du sprichst von Intervallen. Ein Intervall ist definiert durch einen Startwert und einen Endwert. Wir nehmen hier vereinfachend an, dass Start- und Endwert noch zum Intervall zählen (obwohl es bei den gewählten Zahlenwerten unerheblich ist).

Gegeben seien die Intervalle A, B, C, D:
 A = [ 6, 10]
 B = [17, 22]
 C = [ 4,  8]
 D = [15, 18]

Die Vereinigungsmenge ist nun zunächst einmal die Menge aller vier Intervalle. Nicht zwangsläufig lückenlos! Die Aufgabe besteht nun eigentlich darin, die Intervalle zusammenzufassen, wo das möglich ist. Und das ist möglich, wenn sie sich überschneiden (ach, deshalb bist du auf die Schnittmenge gekommen). Und überschneiden tun sie sich dann, wenn der größere der beiden Startwerte kleiner oder gleich dem kleineren der beiden Endwerte ist (bitte am Zahlenstrahl veranschaulichen).

Im Beispiel erkennen wir, dass wir A und C zu *einem* Intervall zusammenfassen können, außerdem die Intervalle B und D, so dass wir die Ergebnismenge erhalten:

( A+C = [4, 10]; B+D = [15,22] )

Eine weitere Zusammenfassung ist nicht möglich, deine Ergebnismenge enthält zwei getrennte Intervalle. Generell musst du natürlich davon ausgehen, dass bei n Intervallen auch die Vereinigungsmenge immer noch aus n getrennten Intervallen besteht.

Oder geht es dir nur um das kleinste Intervall, das seinerseits A bis D enthält, also [4, 22]? Dann bräuchtest du ja nur den kleinsten Startwert und den größten Endwert der n Intervalle zu suchen.

Oder meinst du noch etwas anderes? Dann solltest du das besser erläutern.

So long,
 Martin