Insert Interval
Given a sorted list of non-overlapping intervals and a new interval, insert it and merge where necessary, returning the result still sorted and non-overlapping.
Open on LeetCode ↗Intuition
The input is already sorted and disjoint, so no sort is needed — one linear pass does it. Name the three phases before writing any conditionals: copy what ends before the new interval starts, absorb everything that touches it into one growing block, copy the rest. Two details decide correctness, and both are easy to get backwards: touching endpoints must count as overlapping, and the merged block's low end needs a min, because an existing interval may start earlier than the new one.
Approach
Copy everything that ends before the new interval starts
While intervals[i][1] < newInterval[0], the interval finishes before the new one starts, so append it unchanged. The comparison must be strict <: with <=, an interval merely touching at an endpoint gets copied instead of merged, and [1,3] with [3,5] comes out as two intervals when the answer is one.
Absorb every interval that overlaps
While intervals[i][0] <= hi, the interval starts at or before the current block's end, so it overlaps. Widen the block with lo = min(lo, start) and hi = max(hi, end). Taking the min on the low end matters — an existing interval may begin before the new one does. When the loop ends, push the single merged block.
Copy the rest
Everything remaining starts after the merged block ends, so it is appended untouched. Because the input was sorted, the output is sorted too, with no final sort required. One pass, O(n) time, and O(n) space for the output alone.
Solution & live demo
Edge cases
Both loops skip and the new interval is the entire answer.
Phase one copies nothing, phase two merges nothing, so it is placed first and the rest follow.
Phase one copies all, and the new interval lands at the end.
Phase two runs repeatedly, collapsing all of them into one block — the reason hi uses a running max.