Problem Description

You are given an array of non-overlapping intervals where each interval is represented as [start, end]. The intervals are sorted in ascending order by their start times. You also receive a new interval newInterval = [start, end].

Your task is to insert this new interval into the existing array of intervals while maintaining two conditions:

1. The resulting array should remain sorted by start times
2. There should be no overlapping intervals (if inserting causes overlaps, you need to merge them)

The merging rule is: when two intervals overlap (meaning one interval's end time is greater than or equal to another interval's start time), they should be combined into a single interval that spans from the minimum start time to the maximum end time.

For example:

• If you have intervals [[1,3], [6,9]] and need to insert [2,5], the result would be [[1,5], [6,9]] because [1,3] and [2,5] overlap and merge into [1,5]
• If you have intervals [[1,2], [3,5], [6,7], [8,10], [12,16]] and need to insert [4,8], the result would be [[1,2], [3,10], [12,16]] because [3,5], [4,8], [6,7], and [8,10] all overlap and merge into [3,10]

The solution approach adds the new interval to the existing list and then performs a standard interval merging operation: sort all intervals by start time, then iterate through them, merging any that overlap by extending the end time of the previous interval when needed.

Intuition

When we need to insert a new interval into a sorted list of non-overlapping intervals, we face two main challenges: finding where the new interval fits and handling any overlaps it might create.

The key insight is that this problem is essentially a variant of the classic "merge intervals" problem. Instead of trying to find the exact position to insert and then handle the merging logic separately, we can simplify the approach by treating the new interval as just another interval in the collection.

Think about it this way: if we already had all intervals (including the new one) in a list, we would simply sort them and merge any overlapping ones. The fact that one interval is "new" doesn't really matter for the final result - what matters is that all intervals are properly merged.

This leads us to a straightforward two-step approach:

1. Add the new interval to the existing list
2. Apply the standard interval merging algorithm

The merging algorithm itself follows a natural pattern: after sorting by start times, we traverse the intervals and for each one, we check if it overlaps with the last interval in our result. If it does (meaning the last interval's end time >= current interval's start time), we extend the last interval. If not, we add the current interval as a new separate interval.

This approach elegantly handles all cases:

• If the new interval doesn't overlap with any existing ones, it simply gets placed in its correct sorted position
• If it overlaps with one interval, they merge into one
• If it spans multiple intervals, they all collapse into a single merged interval

The beauty of this solution is its simplicity - rather than writing complex logic to handle insertion and merging separately, we reduce the problem to a well-known pattern that's easier to implement and understand.

Solution Approach

The implementation follows the sorting and interval merging strategy outlined in the reference approach. Let's walk through the code step by step:

Step 1: Add the new interval to the existing list

intervals.append(newInterval)

This simply adds newInterval to the intervals list, treating it like any other interval that needs to be processed.

Step 2: Apply the merge function The core logic is in the merge helper function that performs standard interval merging:

def merge(intervals: List[List[int]]) -> List[List[int]]:
    intervals.sort()
    ans = [intervals[0]]
    for s, e in intervals[1:]:
        if ans[-1][1] < s:
            ans.append([s, e])
        else:
            ans[-1][1] = max(ans[-1][1], e)
    return ans

Let's break down the merging algorithm:

1. Sort the intervals: intervals.sort() sorts all intervals by their start time (Python sorts lists of lists by the first element by default).

2. Initialize the result: ans = [intervals[0]] starts with the first interval in our result list.

3. Iterate through remaining intervals: For each interval [s, e] starting from the second one:

   • Check for overlap: if ans[-1][1] < s
     • If the last interval's end time is less than the current interval's start time, there's no overlap
     • In this case, add the current interval as a new separate interval: ans.append([s, e])
   • Merge if overlapping: else
     • If there is overlap, extend the last interval's end time to cover both intervals
     • Use max(ans[-1][1], e) to ensure we take the furthest end point

Example walkthrough: If we have intervals = [[1,3], [6,9]] and newInterval = [2,5]:

1. After appending: [[1,3], [6,9], [2,5]]
2. After sorting: [[1,3], [2,5], [6,9]]
3. Initialize ans = [[1,3]]
4. Process [2,5]: Since 3 >= 2 (overlap), merge to get ans = [[1,5]]
5. Process [6,9]: Since 5 < 6 (no overlap), append to get ans = [[1,5], [6,9]]

The time complexity is O(n log n) due to sorting, where n is the total number of intervals. The space complexity is O(n) for storing the result array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Existing intervals: [[1,2], [3,5], [6,7], [8,10], [12,16]]
• New interval to insert: [4,8]

Step 1: Add the new interval to the list

intervals = [[1,2], [3,5], [6,7], [8,10], [12,16], [4,8]]

Step 2: Sort all intervals by start time

After sorting: [[1,2], [3,5], [4,8], [6,7], [8,10], [12,16]]

Step 3: Merge overlapping intervals

Initialize result with first interval:

ans = [[1,2]]

Process each remaining interval:

1. Process [3,5]:

   • Check: Is 2 (last interval's end) < 3 (current start)? Yes!
   • No overlap → Append [3,5]
   • ans = [[1,2], [3,5]]

2. Process [4,8]:

   • Check: Is 5 (last interval's end) < 4 (current start)? No! (5 ≥ 4)
   • Overlap detected → Merge by extending end time
   • New end = max(5, 8) = 8
   • ans = [[1,2], [3,8]]

3. Process [6,7]:

   • Check: Is 8 (last interval's end) < 6 (current start)? No! (8 ≥ 6)
   • Overlap detected → Merge by extending end time
   • New end = max(8, 7) = 8 (no change)
   • ans = [[1,2], [3,8]]

4. Process [8,10]:

   • Check: Is 8 (last interval's end) < 8 (current start)? No! (8 ≥ 8)
   • Overlap detected → Merge by extending end time
   • New end = max(8, 10) = 10
   • ans = [[1,2], [3,10]]

5. Process [12,16]:

   • Check: Is 10 (last interval's end) < 12 (current start)? Yes!
   • No overlap → Append [12,16]
   • ans = [[1,2], [3,10], [12,16]]

Final Result: [[1,2], [3,10], [12,16]]

The new interval [4,8] caused four originally separate intervals [3,5], [4,8], [6,7], [8,10] to merge into one consolidated interval [3,10].

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation in the merge function. After appending newInterval to intervals, we have n total intervals (where n is the original number of intervals plus one). The sort() operation takes O(n × log n) time. The subsequent iteration through the sorted intervals takes O(n) time, but this is overshadowed by the sorting complexity.

Space Complexity: O(n)

The space complexity comes from several sources:

• The ans list in the merge function, which in the worst case stores all n intervals when no merging occurs, requiring O(n) space
• The sorting operation may use O(log n) to O(n) additional space depending on the implementation (Python's Timsort uses up to O(n) space in worst case)
• The overall space complexity is therefore O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input List In-Place

The most common pitfall in this solution is that intervals.append(newInterval) modifies the original input list. This can cause unexpected side effects if the caller still needs the original intervals list unchanged.

Problem Example:

original_intervals = [[1,3], [6,9]]
new_interval = [2,5]
solution = Solution()
result = solution.insert(original_intervals, new_interval)
print(original_intervals)  # [[1,3], [6,9], [2,5]] - Original list is modified!

Solution: Create a copy of the intervals list before modification:

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    # Create a new list to avoid modifying the input
    all_intervals = intervals + [newInterval]
    return self.merge_intervals(all_intervals)

2. Inefficient Approach for Already Sorted Intervals

The current solution sorts all intervals even though the input intervals are already sorted. This adds unnecessary O(n log n) complexity when we could achieve O(n) by taking advantage of the pre-sorted nature.

Optimized Solution:

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    result = []
    i = 0
    n = len(intervals)
  
    # Add all intervals that end before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.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
    result.append(newInterval)
  
    # Add all remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
  
    return result

3. Edge Case: Empty Intervals List

While the current solution handles empty lists correctly, it's worth noting that the merge function would fail if called directly with an empty list due to ans = [intervals[0]].

Solution: Add an edge case check:

def merge_intervals(interval_list: List[List[int]]) -> List[List[int]]:
    if not interval_list:
        return []
  
    interval_list.sort()
    merged_result = [interval_list[0]]
    # ... rest of the code

4. Deep Copy Issues with Nested Lists

When creating the result list, using shallow references can lead to unintended modifications:

# Problematic:
ans.append([s, e])  # If [s, e] is a reference to an existing interval

# Better:
ans.append([s, e])  # Creates a new list (which the code already does correctly)