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.