LeetCode 57 Insert Interval - Example and Complexity Analysis

Trace intervals = [[1,2],[3,5],[6,7]], newInterval = [4,6].

Phase 1: intervals before [4,6].

• [1,2]: end=2 < 4. Add [1,2]. Result: [[1,2]].

Phase 2: overlapping intervals.

• [3,5]: 3 < 6 and 5 >= 4. Overlaps! Merge: new = [min(3,4), max(5,6)] = [3,6].
• [6,7]: 6 <= 6 and 7 >= 4. Overlaps! Merge: new = [min(3,6), max(6,7)] = [3,7].

Add merged [3,7]. Result: [[1,2],[3,7]].

Phase 3: no more intervals.

Final: [[1,2],[3,7]].

$O(n)$ time, $O(n)$ space for output.