#57
Insert Interval
Medium Three phases
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Insert a new interval into a sorted list of non-overlapping intervals, merging where needed.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: insert a new interval into a sorted list and merge overlaps.
Why this works: three phases: copy the ones before it, merge the ones that overlap it, copy the ones after it.
Example: [[1,3],[6,9]] + [2,5]
[1,3] overlaps → [1,5][6,9] after → [[1,5],[6,9]]
✦Hints open one at a time
Intervals ending before the new one starts are untouched.
Intervals overlapping it get merged into it.
The rest come after.
↗Approach
One pass in three phases: copy intervals that end before newStart, merge overlapping ones by expanding newInterval's start and end, add it, then copy the remaining.
</>Solution (Java)
import java.util.*;
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList<>();
int i = 0, n = intervals.length;
int start = newInterval[0], end = newInterval[1];
while (i < n && intervals[i][1] < start) res.add(intervals[i++]); // before
while (i < n && intervals[i][0] <= end) { // overlapping
start = Math.min(start, intervals[i][0]);
end = Math.max(end, intervals[i][1]);
i++;
}
res.add(new int[]{start, end});
while (i < n) res.add(intervals[i++]); // after
return res.toArray(new int[0][]);
}
}!Common mistake
Using < vs <= wrongly — intervals that touch (end == start) should merge.
Complexity
- Time: O(n).
- Space: O(n).
Topic: Greedy
🎬 Episodes 69–73: video coming soon