Algorithmen und Datenstrukturen · Middle · Frage 20 von 75
Wie führt man überlappende Intervalle wie [[1,3],[2,6],[8,10]] zusammen?
- 1Jedes Paar von Intervallen vergleichen und überlappende zusammenführen
- 2Nach Start sortieren, dann das letzte Intervall verlängern oder ein neues beginnen
- 3Nach Ende sortieren, dann jedes Intervall entfernen, das ein anderes überlappt
Antwort zeigen
Richtige Antwort: Nach Start sortieren, dann das letzte Intervall verlängern oder ein neues beginnen
Erklärung
Nach Sortierung nach Start überlappt ein Intervall genau dann mit dem vorigen, wenn sein Start nicht nach dem vorigen Ende liegt. Ein Durchlauf ergibt [[1,6],[8,10]]. Die Gesamtkosten sind O(n log n) fürs Sortieren.