Merge Overlapping Intervals in DSA Python - Execution Trace

Concept Flow - Merge Overlapping Intervals

Sort intervals by start

↓

Initialize merged list empty

↓

For each interval

↓

If merged empty or no overlap

↓

Add interval

↓

Continue loop

↓

Return merged

Sort intervals, then go through each. Add if no overlap, else merge with last. Return merged list.

Execution Sample

DSA Python

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)

Merges overlapping intervals from a list and prints the merged intervals.

Execution Table

Step	Operation	Current Interval	Merged List Before	Action	Merged List After	Visual State
1	Sort intervals	[1,3],[2,6],[8,10],[15,18]	[]	Sort by start	[]	[1,3] -> [2,6] -> [8,10] -> [15,18] -> null
2	Check merged empty	[1,3]	[]	merged empty, append	[[1,3]]	[1,3] -> null
3	Check overlap	[2,6]	[[1,3]]	2 <= 3 overlap, merge	[[1,6]]	[1,6] -> null
4	Check overlap	[8,10]	[[1,6]]	8 > 6 no overlap, append	[[1,6],[8,10]]	[1,6] -> [8,10] -> null
5	Check overlap	[15,18]	[[1,6],[8,10]]	15 > 10 no overlap, append	[[1,6],[8,10],[15,18]]	[1,6] -> [8,10] -> [15,18] -> null
6	End loop	N/A	[[1,6],[8,10],[15,18]]	Return merged	[[1,6],[8,10],[15,18]]	[1,6] -> [8,10] -> [15,18] -> null

💡 All intervals processed, merged list returned

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
intervals	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]	[[1,3],[2,6],[8,10],[15,18]]
merged	[]	[[1,3]]	[[1,6]]	[[1,6],[8,10]]	[[1,6],[8,10],[15,18]]	[[1,6],[8,10],[15,18]]
interval (current)	N/A	[1,3]	[2,6]	[8,10]	[15,18]	N/A

Key Moments - 3 Insights

Why do we merge intervals by updating the end of the last merged interval?

Because overlapping intervals share some range, we extend the last merged interval's end to cover the new interval's end if it's larger, as shown in step 3 where [1,3] and [2,6] merge to [1,6].

Why do we append the interval if merged is empty or no overlap?

If merged is empty, there's nothing to merge with, so we add the first interval (step 2). If the current interval starts after the last merged interval ends, they don't overlap, so we add it separately (steps 4 and 5).

Why must intervals be sorted before merging?

Sorting ensures intervals are in order by start time, so overlapping intervals come one after another. Without sorting, we might miss overlaps, as the algorithm relies on comparing current interval with last merged interval (step 1).

Visual Quiz - 3 Questions

Look at the execution table at step 3, what is the merged list after merging?

A [[1,6]]

B [[1,3]]

C [[2,6]]

D [[1,3],[2,6]]

💡 Hint

Check the 'Merged List After' column at step 3 in the execution table.

At which step does the condition 'no overlap' cause the interval to be appended to merged?

A Step 2

B Step 4

C Step 3

D Step 6

💡 Hint

Look for steps where the action says 'append' due to no overlap in the execution table.

If the intervals were not sorted, how would the merged list after step 2 change?

A It would be empty

B It would contain all intervals merged

C It would contain only the first interval unsorted

D It would cause an error

💡 Hint

Refer to the variable_tracker and concept_flow about sorting before merging.

Concept Snapshot

Merge Overlapping Intervals:
1. Sort intervals by start time.
2. Initialize empty merged list.
3. For each interval:
   - If merged empty or no overlap, append.
   - Else merge by updating last interval's end.
4. Return merged list with no overlaps.

Full Transcript

To merge overlapping intervals, first sort the intervals by their start times. Then create an empty list called merged. Go through each interval in order. If merged is empty or the current interval does not overlap with the last interval in merged, add it to merged. If it overlaps, update the end of the last interval in merged to cover the current interval's end if it is larger. Continue until all intervals are processed. The result is a list of intervals with no overlaps.