Insert Interval into Sorted List in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting an interval that merges with one existing interval

What is the output of the code after inserting the interval [4, 8] into the sorted list [[1, 3], [6, 9]]?

DSA Python

def insert_interval(intervals, new_interval):
    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
    return result

intervals = [[1, 3], [6, 9]]
new_interval = [4, 8]
print(insert_interval(intervals, new_interval))

A [[1, 3], [4, 9]]

B [[1, 8], [6, 9]]

C [[1, 3], [4, 8], [6, 9]]

D [[1, 9]]

💡 Hint

Think about how overlapping intervals merge into one.

The new interval [4, 8] overlaps with [6, 9], so they merge into [4, 9]. The first interval [1, 3] stays separate.

❓ Predict Output

intermediate

Output after inserting an interval that does not overlap

What is the output after inserting the interval [10, 12] into the sorted list [[1, 5], [6, 9]]?

DSA Python

def insert_interval(intervals, new_interval):
    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
    return result

intervals = [[1, 5], [6, 9]]
new_interval = [10, 12]
print(insert_interval(intervals, new_interval))

A [[1, 5], [6, 9], [10, 12]]

B [[1, 5], [6, 12]]

C [[10, 12], [1, 5], [6, 9]]

D [[1, 12]]

💡 Hint

Check if the new interval overlaps with any existing intervals.

The new interval [10, 12] does not overlap with any existing intervals, so it is simply appended at the end.

🔧 Debug

advanced

Identify the error in interval insertion code

What error does the following code raise when inserting [2, 5] into [[1, 3], [6, 9]]?

DSA Python

def insert_interval(intervals, new_interval):
    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
    return result

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

A SyntaxError: invalid syntax

B TypeError: unsupported operand type(s)

C IndexError: list index out of range

D No error, outputs [[1, 5], [6, 9]]

💡 Hint

Check the loop condition in the last while loop carefully.

The last while loop uses 'i <= len(intervals)', which tries to access intervals[len(intervals)] causing IndexError.

❓ Predict Output

advanced

Output after inserting an interval that merges multiple intervals

What is the output after inserting [2, 7] into [[1, 3], [4, 6], [8, 10]]?

DSA Python

def insert_interval(intervals, new_interval):
    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
    return result

intervals = [[1, 3], [4, 6], [8, 10]]
new_interval = [2, 7]
print(insert_interval(intervals, new_interval))

A [[2, 7], [8, 10]]

B [[1, 3], [2, 7], [8, 10]]

C [[1, 10]]

D [[1, 7], [8, 10]]

💡 Hint

The new interval overlaps with two existing intervals, so they merge.

The new interval [2, 7] overlaps with [1, 3] and [4, 6], merging into [1, 7]. The last interval stays separate.

🧠 Conceptual

expert

Number of intervals after inserting and merging

Given a sorted list of intervals [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]] and inserting [4, 9], how many intervals will the list have after insertion and merging?

A 2

B 3

C 4

D 5

💡 Hint

Consider which intervals overlap with [4, 9] and merge them.

The new interval [4, 9] overlaps with [3, 5], [6, 7], and [8, 10]. These merge into [3, 10]. The intervals [1, 2] and [12, 16] remain separate, so total intervals are 3.

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