Approach Summary
Three phases: add non-overlapping before, merge overlapping ones, add non-overlapping after.
How to Recognize This Pattern
- Insert and merge a new interval into sorted list
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array