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].

Practice

1. What is the main purpose of merging overlapping intervals in a list of intervals?

easy

A. To remove all intervals that have the same start and end points

B. To sort intervals by their start time only

C. To combine intervals that overlap into a single continuous interval

D. To split intervals into smaller parts

Solution

1. Step 1: Understand overlapping intervals

   Overlapping intervals share some common range, so merging combines them into one continuous interval.

2. Step 2: Purpose of merging

   Merging reduces multiple overlapping intervals into fewer intervals without overlaps.

3. Final Answer:

   To combine intervals that overlap into a single continuous interval -> Option C

4. Quick Check:

   Merging = Combining overlaps [OK]

Hint: Merging means joining overlapping intervals into one [OK]

Common Mistakes:

• Thinking merging means sorting only
• Confusing merging with removing duplicates
• Assuming intervals are split instead of combined

2. Which of the following Python code snippets correctly sorts a list of intervals by their start time before merging?

easy

A. intervals.sort(key=lambda x: x[0], reverse=True)

B. intervals.sort(key=lambda x: x[0])

C. sorted(intervals)

D. intervals.sort(key=lambda x: x[1])

Solution

1. Step 1: Identify sorting key for intervals

   We sort intervals by their start time, which is the first element in each interval.

2. Step 2: Check code correctness

   Using intervals.sort(key=lambda x: x[0]) sorts by start time ascending, which is correct.

3. Final Answer:

   intervals.sort(key=lambda x: x[0]) -> Option B

4. Quick Check:

   Sort by start time = key x[0] [OK]

Hint: Sort intervals by first element before merging [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using sorted(intervals) which returns new list without modifying original
• Sorting in reverse order before merging

3. What is the output of the following Python code?

intervals = [[1,3],[2,6],[8,10],[15,18]]
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])
print(merged)

medium

A. [[1, 6], [8, 10], [15, 18]]

B. [[1, 3], [2, 6], [8, 10], [15, 18]]

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

D. [[1, 3], [8, 10], [15, 18]]

Solution

1. Step 1: Sort intervals by start time

   Intervals after sorting: [[1,3],[2,6],[8,10],[15,18]] (already sorted)

2. Step 2: Merge overlapping intervals

   First interval [1,3] added. Next [2,6] overlaps with [1,3], merged to [1,6]. Then [8,10] no overlap, added. Finally [15,18] no overlap, added.

3. Final Answer:

   [[1, 6], [8, 10], [15, 18]] -> Option A

4. Quick Check:

   Merged intervals = [[1,6],[8,10],[15,18]] [OK]

Hint: Merge if current start ≤ last merged end [OK]

Common Mistakes:

• Not updating the end of merged interval
• Appending intervals without merging
• Incorrectly sorting intervals

4. Find the error in the following code that attempts to merge overlapping intervals:

def merge_intervals(intervals):
    intervals.sort()
    merged = []
    for i in range(len(intervals)):
        if not merged or merged[-1][1] < intervals[i][0]:
            merged.append(intervals[i])
        else:
            merged[-1][1] = max(merged[-1][1], intervals[i][1])
    return merged

print(merge_intervals([(1,4),(2,3)]))

medium

A. Not checking if intervals list is empty before sorting

B. Sorting intervals without a key may cause incorrect order

C. Using range(len(intervals)) instead of iterating directly over intervals

D. Modifying merged[-1][1] directly causes an error because tuples are immutable

Solution

1. Step 1: Identify data type of intervals elements

   Intervals are list of tuples like [(1,4),(2,3)], tuples are immutable.

2. Step 2: Trace the merging process

   After sorting, append first tuple (1,4) to merged. Second overlaps, attempt merged[-1][1] = max(4,3) fails: 'tuple' object does not support item assignment.

3. Final Answer:

   Modifying merged[-1][1] directly causes an error because tuples are immutable -> Option D

4. Quick Check:

   Tuples immutable, can't modify [OK]

Hint: Check if intervals are tuples before modifying elements [OK]

Common Mistakes:

• Assuming all intervals are lists when they might be tuples
• Ignoring immutability errors
• Thinking sorting always needs a key

5. Given a list of intervals where some intervals are nested inside others, how would you modify the merge algorithm to handle intervals like [[1,10],[2,5],[6,9],[11,15]] to produce the correct merged output?

hard

A. Sort intervals by start time and merge by extending the end to max of overlapping intervals

B. Sort intervals by end time and merge by extending the start to min of overlapping intervals

C. Remove nested intervals before merging to avoid duplicates

D. Merge only intervals that have exactly the same start or end points

Solution

1. Step 1: Sort intervals by start time

   Sorting ensures intervals are processed in order, e.g. [[1,10],[2,5],[6,9],[11,15]].

2. Step 2: Merge by extending end to max of overlapping intervals

   When intervals overlap or are nested, update the end of merged interval to the maximum end value.

3. Step 3: Result

   Merged intervals become [[1,10],[11,15]] because [2,5] and [6,9] are inside [1,10].

4. Final Answer:

   Sort intervals by start time and merge by extending the end to max of overlapping intervals -> Option A

5. Quick Check:

   Sort + max end merge = correct nested handling [OK]

Hint: Always extend merged end to max overlapping end [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Removing nested intervals instead of merging
• Merging only exact matches, missing nested cases