Merge Intervals

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Input / Output Format

Input: Array of intervals. Output: Array of merged intervals, sorted by start.

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: [1,3] and [2,6] overlap → merge to [1,6].

Example 2

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Touching at 4 counts as overlap.

Approach Hints

1. Sort intervals by start.
2. Iterate, keeping a merged list. For each interval: if merged is empty or merged.last.end < current.start, push current. Else extend merged.last.end = max(merged.last.end, current.end).
3. Time: O(n log n) for sort. Space: O(n) output.
4. Pitfall: [1,4],[4,5] — treat touching endpoints as overlap (problem-dependent).