Algorithms and Data Structures · Middle · Question 20 of 75
How do you merge overlapping intervals like [[1,3],[2,6],[8,10]]?
- 1Compare every pair of intervals and merge overlapping ones
- ✓Correct answer: Sort by start, then extend the last merged interval or start a new one
- 3Sort by end, then remove every interval that overlaps another
Explanation
After sorting by start, an interval overlaps the previous one exactly when its start is not after the previous end. One pass gives [[1,6],[8,10]]. The total cost is O(n log n) for the sort.