Given a list of intervals, merge every group that overlaps. Return the intervals that are left, which do not overlap.
DSA Animator › DSA Revision › Intervals › Merge Intervals
Remember: sort by start, then merge with the last interval only. Overlap means the next start is at most the current end. The video solves Merge Intervals (LeetCode 56, Medium) with the Sort + Merge pattern from the Intervals topic, and you can replay every step in the interactive Merge Intervals animation.
Given a list of intervals, merge every group that overlaps. Return the intervals that are left, which do not overlap.
For 1 to 3, 2 to 6, 8 to 10 and 15 to 18, the answer is 1 to 6, 8 to 10 and 15 to 18.
Comparing every pair of intervals, and repeating until nothing changes, is O of n squared or worse. After sorting by start, overlapping intervals sit next to each other.
Sort the intervals by start. Walk through them, and compare each one with the last merged interval. If it starts before that one ends, extend the end, otherwise start a new interval.
After sorting, the first interval, 1 to 3, starts the result. 2 to 6 starts at 2, which is before 3, so extend the end to 6. 8 to 10 starts after 6, so it becomes a new interval. 15 to 18 also starts after 10, so it is new as well. The result is 1 to 6, 8 to 10 and 15 to 18.
In code, sort by the start value. If the result is empty, or the current start is greater than the last end, add the interval. Otherwise, set the last end to the larger of the two ends. Sorting dominates, so it's O of n log n time.
Remember: sort by start, then merge with the last interval only. Overlap means the next start is at most the current end.