Problem
LeetCode #57 — one-liner.
- Insert a new interval into a pre-sorted, non-overlapping list and keep it sorted and non-overlapping.
Key insight
Three phases, no re-sort.
- Input is already sorted — you don’t need
O(n log n). - Split the walk into: (1) before the new one, (2) overlap with new one, (3) after.
- In the merge phase, absorb overlaps into
newIntervalwithminon start,maxon end. Append it once, then flush the tail.
Solution template
Three while-loops in a row.
# 1. before
while i < n and intervals[i][1] < newInterval[0]: ...
# 2. merge
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
# 3. after
while i < n: ...Complexity
Linear because the input is sorted.
- Time
O(n)— single linear pass, no sort. - Space
O(n)— output list.
Edge cases
The four corners.
- New interval entirely before everything → phases 1 & 2 do nothing.
- New interval entirely after everything → phase 1 flushes everything, phase 2 just appends new.
- New interval swallows existing ones → phase 2 merges them all.
- Empty input → return
[newInterval].
Comments
Comments are disabled in this environment. Set
PUBLIC_GISCUS_REPO,PUBLIC_GISCUS_REPO_ID, andPUBLIC_GISCUS_CATEGORY_IDto enable.