Merge Overlapping Intervals in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging intervals with partial overlaps

What is the output of the following code that merges overlapping intervals?

DSA Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge_intervals(intervals))

A [[1, 6], [8, 18]]

B [[1, 6], [8, 10], [15, 18]]

C [[1, 3], [2, 6], [8, 10], [15, 18]]

D [[1, 10], [15, 18]]

💡 Hint

Remember to sort intervals by their start time before merging.

The code sorts intervals by start time. It merges [1,3] and [2,6] into [1,6]. The others remain separate.

❓ Predict Output

intermediate

Output when intervals are fully overlapping

What is the output of this code merging fully overlapping intervals?

DSA Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

intervals = [[1,10],[2,5],[3,7],[8,9]]
print(merge_intervals(intervals))

A [[1, 7], [8, 9]]

B [[1, 5], [3, 7], [8, 9]]

C [[1, 10]]

D [[1, 9]]

💡 Hint

All intervals overlap inside the first interval.

All intervals overlap within [1,10], so they merge into one big interval.

🔧 Debug

advanced

Identify the error in merging intervals code

What error does this code produce when merging intervals?

DSA Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] <= interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

intervals = [[1,4],[4,5]]
print(merge_intervals(intervals))

A [[1, 5]]

B IndexError

C TypeError

D [[1, 4], [4, 5]]

💡 Hint

Check the condition for merging intervals that touch at edges.

The condition uses <= which treats touching intervals as non-overlapping, so they remain separate.

❓ Predict Output

advanced

Output of merging intervals with nested intervals

What is the output of this code merging nested intervals?

DSA Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

intervals = [[1,10],[2,3],[4,5],[6,7],[8,9]]
print(merge_intervals(intervals))

A [[1, 10]]

B [[1, 3], [4, 5], [6, 7], [8, 9]]

C [[1, 5], [6, 7], [8, 9]]

D [[1, 7], [8, 9]]

💡 Hint

Nested intervals inside a bigger interval merge into it.

All smaller intervals are inside [1,10], so they merge into one big interval.

❓ Predict Output

expert

Output of merging intervals with unsorted input and duplicates

What is the output of this code merging intervals with duplicates and unsorted input?

DSA Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

intervals = [[5,7],[1,3],[2,6],[8,10],[1,3],[15,18],[17,20]]
print(merge_intervals(intervals))

A [[1, 7], [8, 10], [15, 20]]

B [[1, 6], [5, 7], [8, 10], [15, 20]]

C [[1, 3], [2, 6], [5, 7], [8, 10], [15, 18], [17, 20]]

D [[1, 7], [8, 10], [15, 18], [17, 20]]

💡 Hint

Duplicates and overlapping intervals merge into one.

Intervals [1,3], [2,6], [5,7], and duplicate [1,3] merge into [1,7]. Intervals [15,18] and [17,20] merge into [15,20].