0057.Insert Interval

• Link: 57. Insert Interval - Medium
• Track: NeetCode150

Question

Restate the problem

• Given a list of non-overlapping intervals sorted in ascending order
• Insert newInterval into the list
• Merge if overlapping (including touching: end == start counts as overlap)
• Return the resulting list (still sorted, non-overlapping)

Case

• intervals = [[3,5],[6,7]] newInterval = [1,2] → [[1,2],[3,5],[6,7]]
• intervals = [[1,3],[6,9]] newInterval = [2,5] → [[1,5],[6,9]]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Phase Scan	$O(n)$	$O(n)$
Method 2	Insert + merge	$O(nlogn)$	$O(n)$

Method 1 - Phase Scan

Key idea:

• Do a one-pass 3-phase scan: append intervals before newInterval, merge all overlaps into newInterval, then append the res.
• keep expanding newInterval while intervals overlap.
• 一次遍历分三段：先放进所有在 newInterval 左边的区间，再把所有重叠区间合并进 newInterval，最后把右边剩下的区间加进去。(遇到重叠区间时不断扩大 newInterval)

Approach

• Add all intervals that end before newInterval starts: end < newStart
• Merge all intervals that overlap with newInterval: start ⇐ newEnd
• Expand newInterval by updating its start/end
• Append the merged newInterval once
• Append the rest intervals

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        
        res = []
        idx = 0
        # 1) add all intervals completely before newInterval
        while idx < n and intervals[idx][1] < newInterval[0]:            
            res.append(intervals[idx])
            idx += 1
        
        # 2) merge overlaps into newInterval
        while idx < n and intervals[idx][0] <= newInterval[1]:
            newInterval[0] = min(intervals[idx][0], newInterval[0])
            newInterval[1] = max(intervals[idx][1], newInterval[1])
            idx += 1
        res.append(newInterval)
        
        # 3) append the rest
        while idx < n:
            res.append(intervals[idx])
            idx += 1
        
        return res

Method 2 - Insert + merge

Key idea:

• Insert newInterval, then solve it exactly like Merge Intervals.
• 先把 newInterval 插入数组，再按照 Merge Intervals 的方法排序并合并。

Approach

1. Append newInterval to intervals
2. Sort intervals by start
3. Merge overlapping intervals using the standard merge algorithm

Complexity

• Time Complexity: $O(nlogn)$
• Space Complexity: $O(n)$

Code

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        intervals.sort(key = lambda x:x[0])
 
        merged = []
        idx = 0
        while idx < len(intervals):
            start, end = intervals[idx]
            if merged and merged[-1][1] >= start:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
 
            idx += 1
 
        return merged

---

Common Mistake