Insert Interval into Sorted List in DSA Python

Mental Model

We add a new time slot into a list of sorted time slots and merge any that overlap to keep the list neat and ordered.

Analogy: Imagine you have a schedule with booked meetings sorted by time. You want to add a new meeting and combine any that clash so your schedule stays clear and organized.

Intervals list:
[1,3] -> [6,9] -> null
Insert interval:
[2,5]

Dry Run Walkthrough

Input: intervals: [1,3] -> [6,9], insert [2,5]

Goal: Insert [2,5] into the sorted list and merge overlapping intervals to keep the list sorted and non-overlapping.

Step 1: Add all intervals before the new interval that end before it starts

[1,3] -> null (added), remaining intervals: [6,9]

Why: Intervals ending before new interval start do not overlap and can be kept as is

Step 2: Merge overlapping intervals with the new interval

Merge [1,3] and [2,5] into [1,5], remaining intervals: [6,9]

Why: Intervals overlap, so we combine them into one bigger interval

Step 3: Add remaining intervals after the new merged interval

[1,5] -> [6,9] -> null

Why: Remaining intervals start after the merged interval ends, so just add them

Result:

[1,5] -> [6,9] -> null

Annotated Code

DSA Python

from typing import List

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

# Driver code
sol = Solution()
intervals = [[1,3],[6,9]]
newInterval = [2,5]
res = sol.insert(intervals, newInterval)
print(' -> '.join(f"[{s},{e}]" for s,e in res) + ' -> null')

while i < n and intervals[i][1] < newInterval[0]:

Add intervals that end before new interval starts -- no overlap

while i < n and intervals[i][0] <= newInterval[1]:

Merge overlapping intervals by updating newInterval boundaries

result.append(newInterval)

Add the merged new interval to result

while i < n:

Add remaining intervals after merged interval

Output

[1,5] -> [6,9] -> null

Complexity Analysis

Time: O(n) because we scan through the list of intervals once

Space: O(n) because we create a new list to store the merged intervals

vs Alternative: Naive approach might insert and then sort or merge repeatedly, costing O(n log n) or more

Edge Cases

Empty intervals list

Returns list with only the new interval

DSA Python

while i < n and intervals[i][1] < newInterval[0]:

New interval does not overlap and goes at the end

New interval is appended after all existing intervals

DSA Python

while i < n and intervals[i][1] < newInterval[0]:

New interval overlaps all intervals

All intervals merged into one big interval

DSA Python

while i < n and intervals[i][0] <= newInterval[1]:

When to Use This Pattern

When you need to insert and merge intervals in a sorted list, use the insert-and-merge pattern to keep intervals sorted and non-overlapping efficiently.

Common Mistakes

Mistake: Not merging all overlapping intervals, only merging the first one
Fix: Use a loop to merge all intervals overlapping with the new interval

Mistake: Appending new interval before merging overlaps
Fix: Merge first, then append the merged interval

Summary

Inserts a new interval into a sorted list of intervals and merges any overlaps.

Use when you have sorted intervals and want to add a new one without breaking order or overlap rules.

The key is to add intervals before, merge overlapping ones, then add the rest.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping

B. To replace the first interval with the new interval regardless of overlap

C. To insert the new interval at the end without checking for overlaps

D. To delete all intervals that come after the new interval

Solution

1. Step 1: Understand the problem requirement

   The goal is to insert a new interval into a sorted list of intervals without overlaps.

2. Step 2: Merge overlapping intervals after insertion

   After inserting, merge any intervals that overlap to maintain the sorted, non-overlapping property.

3. Final Answer:

   To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping -> Option A

4. Quick Check:

   Insert and merge intervals = To add the new interval and merge any overlapping intervals to keep the list sorted and non-overlapping [OK]

Hint: Insert then merge overlapping intervals to keep list sorted [OK]

Common Mistakes:

• Ignoring merging after insertion
• Inserting without maintaining order
• Replacing intervals incorrectly

2. Which of the following Python code snippets correctly inserts a new interval into a sorted list of intervals without merging?

easy

A. intervals.remove(new_interval)

B. intervals.append(new_interval)

C. intervals.sort()

D. intervals.insert(2, new_interval)

Solution

1. Step 1: Identify correct insertion method

   Using insert(index, element) places the new interval at the correct position without losing order.

2. Step 2: Understand other options

   append adds at end without order, sort only sorts but doesn't insert, remove deletes an element.

3. Final Answer:

   intervals.insert(2, new_interval) -> Option D

4. Quick Check:

   Use insert() to add at specific position [OK]

Hint: Use insert(index, value) to place interval correctly [OK]

Common Mistakes:

• Using append without sorting
• Using remove instead of insert
• Relying on sort without insertion

3. What is the output of the following code?

intervals = [[1,3],[6,9]]
new_interval = [2,5]

# Insert new_interval and merge
result = []
i = 0
while i < len(intervals) and intervals[i][1] < new_interval[0]:
    result.append(intervals[i])
    i += 1
while i < len(intervals) and intervals[i][0] <= new_interval[1]:
    new_interval[0] = min(new_interval[0], intervals[i][0])
    new_interval[1] = max(new_interval[1], intervals[i][1])
    i += 1
result.append(new_interval)
while i < len(intervals):
    result.append(intervals[i])
    i += 1
print(result)

medium

A. [[2, 5], [6, 9]]

B. [[1, 3], [2, 5], [6, 9]]

C. [[1, 5], [6, 9]]

D. [[1, 3], [6, 9], [2, 5]]

Solution

1. Step 1: Add intervals before new_interval

   The first while loop checks if intervals[i][1] < new_interval[0]. For i=0, 3 < 2 is false, so no intervals added before. result = [].

2. Step 2: Merge overlapping intervals

   Intervals overlapping with new_interval [2,5] are [1,3] and [2,5] merged to [1,5].

3. Step 3: Add remaining intervals

   Remaining interval [6,9] is added after merged interval.

4. Final Answer:

   [[1, 5], [6, 9]] -> Option C

5. Quick Check:

   Merged intervals = [[1, 5], [6, 9]] [OK]

Hint: Merge intervals overlapping new_interval boundaries [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new_interval without merging
• Incorrect loop conditions

4. The following code tries to insert and merge a new interval but produces incorrect output. What is the bug?

def insert_interval(intervals, new_interval):
    result = []
    for interval in intervals:
        if interval[1] < new_interval[0]:
            result.append(interval)
        elif interval[0] > new_interval[1]:
            result.append(new_interval)
        else:
            new_interval[0] = min(new_interval[0], interval[0])
            new_interval[1] = max(new_interval[1], interval[1])
    result.append(new_interval)
    return result

print(insert_interval([[1,3],[6,9]], [2,5]))

medium

A. Appending new_interval inside loop causes duplicates

B. Not updating new_interval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in conditions

Solution

1. Step 1: Analyze loop behavior

   Appending new_interval inside the loop when interval[0] > new_interval[1] causes multiple appends.

2. Step 2: Understand consequences

   This leads to duplicates and incorrect order in the result list.

3. Final Answer:

   Appending new_interval inside loop causes duplicates -> Option A

4. Quick Check:

   Append new_interval once after loop [OK]

Hint: Append merged interval only once after loop ends [OK]

Common Mistakes:

• Appending inside loop multiple times
• Not merging intervals properly
• Confusing interval boundaries

5. Given a sorted list of intervals [[1,2],[3,5],[6,7],[8,10],[12,16]] and a new interval [4,8], what is the final list after inserting and merging?

hard

A. [[1,2],[3,5],[6,7],[8,10],[4,8],[12,16]]

B. [[1,2],[3,10],[12,16]]

C. [[1,2],[4,8],[12,16]]

D. [[1,2],[3,8],[12,16]]

Solution

1. Step 1: Identify intervals overlapping with [4,8]

   Intervals [3,5], [6,7], and [8,10] overlap with [4,8].

2. Step 2: Merge overlapping intervals

   Merge [3,5], [6,7], [8,10], and [4,8] into [3,10].

3. Step 3: Combine with non-overlapping intervals

   Keep [1,2] and [12,16] as is, final list is [[1,2],[3,10],[12,16]].

4. Final Answer:

   [[1,2],[3,10],[12,16]] -> Option B

5. Quick Check:

   Merged intervals = [[1,2],[3,10],[12,16]] [OK]

Hint: Merge all intervals overlapping new interval boundaries [OK]

Common Mistakes:

• Not merging all overlapping intervals
• Appending new interval without merging
• Incorrectly splitting intervals