Algorithmus zur Berechnung einer Vereinigungsmenge

[Vinzenz Mai]

Hallo,

ich zerbrechne mir gerade meinen Kopf über folgendes Problem.
Ich versuche das Problem erstmal so abstrakt wie möglich zu beschreiben. Wenn ihr später konkrete Lösungswege, evtl. mit Javascript beschreibt, wäre das super!

Problemstellung: Ich möchte einen Algorithmus programmieren der mir von n-vielen verschiedenen Intervallen, die Vereinigungsmenge wiedergibt.

die Vereinigungsmenge besteht somit aus einer Anzahl von 1 bis n verschiedenen Intervallen, je nach Datenlage.

Eine Idee wäre es, die Vereinigungsmenge mit einem zu InsertSort vergleichbaren Verfahren zusammenzustellen, wobei nach Intervallanfang sortiert wäre (geht natürlich genauso auch absteigend nach Intervallende). Die Einfügeoperation muss so modifiziert werden, dass Intervalle zusammengefasst werden, falls nötig. Da in der Vereinigungsmenge nur disjunkte Intervalle vorliegen, sollten sowohl Einfügeposition als auch zusammenzufassenden Intervalle effizient zu finden sein. Ob das Verfahren insgesamt effizient ist, hängt unter anderem von dem Aufwand ab, der für die Einfügeoperation und das Zusammenfassen erforderlich ist.

Freundliche Grüße

Vinzenz