Core Insight After sorting, overlap decisions depend only on the active interval and the next start.
Common Pitfall Compare the next start against the current end, not against the original unsorted input.
Description
Insert a new interval and merge if necessary.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
array
Implementation Plan Translate the invariant into these small, testable moves.
- Sort by the relevant endpoint.
- Initialize the active interval.
- Merge or select based on overlap.
- Update the active boundary.
def insert(intervals, newInterval):
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [min(newInterval[0], intervals[i][0]),
max(newInterval[1], intervals[i][1])]
res.append(newInterval)
return res