Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and the end time of the ith interval. intervals is initially sorted in ascending order by start_i.

You are given another interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and also intervals still does not have any overlapping intervals. You may merge the overlapping intervals if needed.

Return intervals after adding newInterval.

Note: Intervals are non-overlapping if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.

Examples

• 0 ≤ intervals.length ≤ 1000
• newInterval.length == intervals[i].length == 2
• 0 ≤ start ≤ end ≤ 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• Arrays - Basic iteration and manipulation of array elements
• Interval Problems - Understanding how to represent and compare ranges (start, end)
• Merging Logic - Detecting overlap between intervals and combining them into a single interval
• Binary Search (for optimized solution) - Finding insertion points in sorted arrays

1. Linear Search

Intuition

We are given a list of non-overlapping intervals sorted by start time, and we need to insert newInterval into the list while keeping the result sorted and non-overlapping.

Since the intervals are already sorted, we can process them in one pass and split the work into three simple parts:

• Intervals completely before newInterval: These do not overlap, so we can add them directly to the result.
• Intervals that overlap with newInterval: While there is overlap, we merge them by expanding newInterval (new start = minimum of starts, new end = maximum of ends).
• Intervals completely after the merged newInterval: These also do not overlap, so we add them directly.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        res = []

        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

        while i < n:
            res.append(intervals[i])
            i += 1

        return res

Time Complexity: O(n)
Space Complexity: O(1) extra space, O(n) space for the output list.

2. Binary Search

Intuition

We are given a list of non-overlapping intervals sorted by start time. A simple idea is:

• Use binary search to find the correct position where newInterval should be inserted based on its start time.
• After inserting, the list is still sorted by start time.
• Then we do a normal merge intervals pass: if the current interval does not overlap the last interval in the result, append it; otherwise merge them by extending the end.

Binary search helps us avoid scanning from the beginning just to find the insertion position.

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]

        n = len(intervals)
        target = newInterval[0]
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            if intervals[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1

        intervals.insert(left, newInterval)

        res = []
        for interval in intervals:
            if not res or res[-1][1] < interval[0]:
                res.append(interval)
            else:
                res[-1][1] = max(res[-1][1], interval[1])
        return res

Time Complexity: O(n) (since insertion takes O(n) and the merge loop takes O(n))
Space Complexity: O(n) space for the output list.

3. Greedy

Intuition

A greedy approach works because as we scan from left to right, every interval falls into one of three cases relative to newInterval:

• Completely after newInterval: If newInterval ends before the current interval starts, there will be no overlap with any later interval either. So we can safely place newInterval here and return the answer immediately.
• Completely before newInterval: If the current interval ends before newInterval starts, it can be added to the result unchanged.
• Overlapping with newInterval: If they overlap, we merge them by expanding newInterval to cover both ranges.

Common Pitfalls

Incorrect Overlap Detection

Using the wrong condition to detect overlapping intervals leads to incorrect merging. Two intervals [a, b] and [c, d] overlap when a <= d AND c <= b. A common mistake is checking only one direction or using strict inequality (< instead of <=), which fails for adjacent intervals like [1, 2] and [2, 3] that should merge.

Forgetting to Add the New Interval at the End

When the new interval belongs after all existing intervals (its start is greater than all existing ends), the merging loop never triggers and the new interval is never added. The algorithm must append the new interval to the result after the loop completes if it was not already inserted.

Mutating the Original Input Array

Some solutions modify the newInterval array during merging, which can cause issues if the caller expects the original input to remain unchanged. In languages where arrays are passed by reference, this side effect may lead to unexpected behavior in the calling code.