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.