Insert Interval
Insert Interval is a medium Intervals problem from the Blind 75. The key pattern is linear merge, and a good solution runs in O(n) time.
Problem
Insert an interval into sorted non-overlapping intervals, merging every overlap.
Examples
Example 1
Input
{"intervals":[[1,2],[5,7],[9,12]],"newInterval":[6,10]}Output
[[1,2],[5,12]]Example 2
Input
{"intervals":[[2,4],[7,9]],"newInterval":[3,6]}Output
[[2,6],[7,9]]Example 3
Input
{"intervals":[[1,5]],"newInterval":[6,8]}Output
[[1,5],[6,8]]Approach
Copy intervals that end before the new one, merge every interval that overlaps it into a single span, then copy the rest.
| Pattern | Linear merge |
|---|---|
| Time | O(n) |
| Space | O(n) |
Watch out for
The input is already sorted and non-overlapping; keep it that way.