The problem
An interval [start, end] covers every point from start to end. You are given a list of intervals that do not overlap, sorted by start, and one more interval, newInterval.
Insert it, merging whatever it overlaps, and return the list — still sorted, still without overlaps.
Examples
- Input
intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
- Output
[[1, 5], [6, 9]]
- Input
intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
- Output
[[1, 2], [3, 10], [12, 16]]
Constraints
- 0 ≤ intervals.length ≤ 10⁴
- 0 ≤ start ≤ end ≤ 10⁵
intervalsis sorted by start and has no overlaps.
The idea
The list is already sorted, so it falls into three runs: intervals that end before the new one starts (untouched), intervals that overlap it, and intervals that start after it ends (untouched).
Copy the first run. Then absorb every overlapping interval into the new one, stretching its start down to the smallest start and its end up to the largest end. Add it, and copy the rest. One pass, no sorting.
- Time
- O(n)
- Space
- O(n) — the answer
Solution · every language run against every case
class Solution: def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: out, i, n = [], 0, len(intervals) s, e = newInterval while i < n and intervals[i][1] < s: # wholly before the new one: keep as it is out.append(intervals[i]) i += 1 while i < n and intervals[i][0] <= e: # overlapping it: absorb into one interval s, e = min(s, intervals[i][0]), max(e, intervals[i][1]) i += 1 out.append([s, e]) out.extend(intervals[i:]) # wholly after: keep as they are return out