You are given a list of non-overlapping intervals sorted by start, and one more interval newInterval. Insert newInterval so the list stays sorted and non-overlapping, merging intervals where needed, and return the new list.
[4,8] overlaps [3,5], [6,7] and [8,10].- 0 <= intervals.length <= 10^4
- intervals is sorted by start and has no overlaps
- 0 <= start <= end <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
One option is to append the new interval and run Merge Intervals, which costs O(n log n) for the sort. Since the list is already sorted, a single pass is enough. Intervals that end before the new one starts are untouched. The intervals that overlap the new one form one contiguous run; we absorb them by widening newInterval to the min start and max end. Everything after that run is also untouched.
Algorithm
- Copy every interval with
end < newInterval[0]intores. - While the next interval has
start <= newInterval[1], widennewIntervalto[min(starts), max(ends)]. - Append the widened
newInterval. - Copy all remaining intervals and return
res.
O(n)Space: O(n) for the output[1,5] and [5,7] must merge, so use <= not <.class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: res = [] i, n = 0, len(intervals) s, e = newInterval while i < n and intervals[i][1] < s: # fully before res.append(intervals[i]) i += 1 while i < n and intervals[i][0] <= e: # overlapping run s = min(s, intervals[i][0]) e = max(e, intervals[i][1]) i += 1 res.append([s, e]) res.extend(intervals[i:]) # fully after return res