LeetCode 56 Merge Intervals - Example and Complexity Analysis

Trace intervals = [[1,3],[2,6],[8,10],[15,18]].

Already sorted by start.

result = [[1,3]] (first interval)

[2,6]: 2 <= 3 (overlaps). Extend: result = [[1,6]].

[8,10]: 8 > 6 (no overlap). Add: result = [[1,6],[8,10]].

[15,18]: 15 > 10 (no overlap). Add: result = [[1,6],[8,10],[15,18]].

Final: [[1,6],[8,10],[15,18]].

$O(n \log n)$ time for sorting. $O(n)$ space for result.