Back to solutions

Insert Interval

MediumArrays

Insert a new interval into a sorted list and merge overlaps.

Open problem
Constraints
  • 0 <= n <= 10^4
  • intervals are sorted and non-overlapping

Three phases

Time O(n)Space O(n)

Because the list is already sorted, process it in three phases: copy intervals entirely before the new one, merge all intervals that overlap the new one by widening its bounds, then copy the rest. The single merged interval is inserted between the two copied groups.

Key terms
non-overlapping:
No two intervals share any point; the input keeps this property.
widening:
Expanding the new interval's start/end to swallow every overlapping interval.
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int> ni) {
    vector<vector<int>> res; size_t i = 0, n = intervals.size();
    while (i < n && intervals[i][1] < ni[0]) res.push_back(intervals[i++]);
    while (i < n && intervals[i][0] <= ni[1]) {
        ni[0] = min(ni[0], intervals[i][0]);
        ni[1] = max(ni[1], intervals[i][1]); i++;
    }
    res.push_back(ni);
    while (i < n) res.push_back(intervals[i++]);
    return res;
}
Step by step
  1. Append every interval that ends before the new interval starts (no overlap).
  2. While an interval starts at or before the new interval's end, merge it by taking min start and max end.
  3. Append the merged new interval.
  4. Append all remaining intervals unchanged.