Eine Funktion MERGE die eine Liste von Intervallen entgegennimmt und als Ergebnis wiederum eine Liste von Intervallen zurückgibt. Im Ergebnis sollen alle sich überlappenden Intervalle gemerged sein. Alle nicht überlappenden Intervalle bleiben unberührt.
- Wie ist die Laufzeit Ihres Programms ? O(n Log n) time
- Wie kann die Robustheit sichergestellt werden, vor allem auch mit Hinblick auf sehr große Eingaben ? Teilen und erobern
- Wie verhält sich der Speicherverbrauch ihres Programms ? Das brauchst O(n) Speicherplatz