Problem Description

You are given an array of non-overlapping intervals, intervals, where each interval is represented as a pair [start, end] and is sorted in ascending order by its start value. You are also given another interval, newInterval, which you need to insert into intervals so that the resulting array is still sorted and contains no overlapping intervals.

If newInterval overlaps with existing intervals, you must merge all overlapping intervals into a single interval. The output should be the updated list of intervals.

• Each interval is a pair of integers [start, end] with start <= end.
• No two intervals in intervals overlap before insertion.
• Return the result as a list of intervals, each in the form [start, end], sorted by their start times.

Thought Process

At first glance, you might think of inserting newInterval into the correct position and then scanning the entire array to merge any overlapping intervals. However, since intervals is already sorted and non-overlapping, we can take advantage of this structure to efficiently insert and merge in a single pass.

The key realization is that there are three types of intervals in relation to newInterval:

• Intervals that end before newInterval starts (no overlap, appear before).
• Intervals that overlap with newInterval (need to merge).
• Intervals that start after newInterval ends (no overlap, appear after).

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Initialize an empty result list. This will store the final set of intervals.
2. Iterate over each interval in intervals:
   • If the current interval ends before newInterval starts: Add it directly to the result list. There is no overlap.
   • If the current interval starts after newInterval ends: Add newInterval to the result (if not already added), then add all remaining intervals as they are. We can stop merging at this point.
   • If the current interval overlaps with newInterval: Merge them by updating newInterval to cover the union of both intervals. Do not add anything to the result yet.
3. After the loop, add the last newInterval to the result. This covers the case where newInterval extends beyond all existing intervals.
4. Return the result list.

This approach ensures we only traverse the list once, and only merge when necessary, making it efficient and easy to understand.

Example Walkthrough

Let's walk through an example:

Input:
intervals = [[1,3],[6,9]]
newInterval = [2,5]

• The first interval is [1,3]. Since 3 >= 2 (overlap), we merge [1,3] and [2,5] to get [1,5].
• The next interval is [6,9]. Since 6 > 5 (no overlap), we add the merged interval [1,5] to the result, then add [6,9].

Output: [[1,5],[6,9]]

The process efficiently merges only where necessary and preserves the sorted, non-overlapping property.

Time and Space Complexity

Brute-force approach: Inserting the interval, sorting, and then merging all intervals would take O(n \log n) time due to sorting, and O(n) space.

Optimized approach (our solution): We make a single pass through the intervals, so the time complexity is O(n), where n is the number of intervals. Space complexity is also O(n) due to the result list.

Summary

The Insert Interval problem leverages the sorted, non-overlapping nature of the input to allow a one-pass, linear-time solution. By categorizing intervals as before, overlapping, or after the new interval, we merge only where necessary and build the result efficiently. This approach is both elegant and practical, illustrating the power of using input constraints to simplify complex problems.

Code Implementation

class Solution:
    def insert(self, intervals, newInterval):
        res = []
        i = 0
        n = len(intervals)
        
        # Add all intervals before newInterval
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1
        
        # Merge all overlapping intervals with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)
        
        # Add all intervals after newInterval
        while i < n:
            res.append(intervals[i])
            i += 1
        
        return res
      

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        int i = 0, n = intervals.size();
        
        // Add all intervals before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i++;
        }
        
        // Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);
        
        // Add all intervals after newInterval
        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};
      

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> res = new ArrayList<>();
        int i = 0, n = intervals.length;
        
        // Add all intervals before newInterval
        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }
        
        // Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.add(newInterval);
        
        // Add all intervals after newInterval
        while (i < n) {
            res.add(intervals[i]);
            i++;
        }
        
        return res.toArray(new int[res.size()][]);
    }
}
      

var insert = function(intervals, newInterval) {
    const res = [];
    let i = 0, n = intervals.length;
    
    // Add all intervals before newInterval
    while (i < n && intervals[i][1] < newInterval[0]) {
        res.push(intervals[i]);
        i++;
    }
    
    // Merge all overlapping intervals with newInterval
    while (i < n && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
        newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
        i++;
    }
    res.push(newInterval);
    
    // Add all intervals after newInterval
    while (i < n) {
        res.push(intervals[i]);
        i++;
    }
    
    return res;
};