DSA Pattern: Merge Intervals

Merging overlapping intervals is a staple interview problem for array manipulation and sorting.

Algorithm

1. Sort intervals by start value.
2. Initialize merged list with the first interval.
3. For each subsequent interval curr:
   • If curr.start <= lastMerged.end, overlap exists! Update lastMerged.end = max(lastMerged.end, curr.end).
   • Otherwise, no overlap. Push curr into merged.

Complexity: Time O(N log N) due to sorting. Space O(N) for output.