Sort the intervals by start, then sweep once: each interval either overlaps the last merged interval (stretch its end) or starts after it ends (begin a new one). Sorting is what makes one look back enough.
- Average time
- O(n log n)
- Space
- O(n)
Sort the intervals by start, then sweep once: each interval either overlaps the last merged interval (stretch its end) or starts after it ends (begin a new one). Sorting is what makes one look back enough.