LeetEye LeetEye
Medium Intervals ~5 min

Insert Interval

intervals insert-interval

Problem

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still has no overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Examples

Example 1
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Key Insight

Three phases: intervals before new (no overlap), merge with new (overlap), intervals after new (no overlap).

Three phases: (1) add intervals ending before new starts, (2) merge all overlapping intervals with new, (3) add intervals starting after new ends.

How to Approach This Problem

Pattern Recognition: When you see keywords like insert interval intervals, think Intervals.

Step-by-Step Reasoning

1 Interval [a, b] is completely before newInterval [x, y] if:
Answer: b < x
If interval ends before new starts, no overlap. Add to result as-is.
2 Interval [a, b] is completely after newInterval [x, y] if:
Answer: a > y
If interval starts after new ends, no overlap. Add to result as-is.
3 Interval [a, b] overlaps with [x, y] if:
Answer: a <= y AND b >= x
Overlap when neither is completely before nor after the other.
4 When merging [a, b] into [x, y]:
Answer: new_start = min(a, x), new_end = max(b, y)
Merged interval spans from earliest start to latest end.
5 We process intervals:
Answer: By start time (given sorted)
Input is sorted by start. Process linearly: before, overlap, after.

Solution

def insert(intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    result = []
    i = 0
    n = len(intervals)
    
    # Phase 1: Add intervals ending before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # Phase 2: Merge overlapping intervals
    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
    result.append(newInterval)
    
    # Phase 3: Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

Complexity Analysis

Time O(n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Intervals problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye