💡 The merged interval becomes [1,6], combining the two overlapping intervals.
traverse
Move to next interval (i=2)
Increment 'i' to 2 to compare the third interval with the last merged interval at 'index'.
💡 We continue checking if the next interval overlaps with the merged intervals so far.
Line:for i in range(1, len(intervals)):
💡 Iteration proceeds to the next interval for comparison.
compare
Compare intervals[2] start with intervals[index] end
Check if intervals[2][0] (8) is less than or equal to intervals[index][1] (6) to detect overlap.
💡 If current interval starts after last merged ends, no overlap occurs.
Line:if intervals[i][0] <= intervals[index][1]:
💡 Intervals [1,6] and [8,10] do not overlap, so we must move 'index' and copy the current interval.
insert
Increment index and copy intervals[i] to intervals[index]
Since no overlap, move 'index' forward and copy the current interval to that position.
💡 This step adds a new merged interval to the list at the next position.
Line:index += 1
intervals[index] = intervals[i]
💡 The merged intervals list now includes [1,6] and [8,10] at positions 0 and 1.
traverse
Move to next interval (i=3)
Increment 'i' to 3 to compare the fourth interval with the last merged interval at 'index'.
💡 We continue checking if the next interval overlaps with the merged intervals so far.
Line:for i in range(1, len(intervals)):
💡 Iteration proceeds to the next interval for comparison.
compare
Compare intervals[3] start with intervals[index] end
Check if intervals[3][0] (15) is less than or equal to intervals[index][1] (10) to detect overlap.
💡 If current interval starts after last merged ends, no overlap occurs.
Line:if intervals[i][0] <= intervals[index][1]:
💡 Intervals [8,10] and [15,18] do not overlap, so we must move 'index' and copy the current interval.
insert
Increment index and copy intervals[i] to intervals[index]
Since no overlap, move 'index' forward and copy the current interval to that position.
💡 This step adds the last interval to the merged list.
Line:index += 1
intervals[index] = intervals[i]
💡 The merged intervals list now includes [1,6], [8,10], and [15,18].
reconstruct
Iteration complete, return merged intervals slice
The loop ends, and the algorithm returns the slice of intervals up to index+1 as the merged result.
💡 Only the first index+1 intervals are valid merged intervals; the rest are leftover copies.
Line:return intervals[:index+1]
💡 The final merged intervals are [[1,6],[8,10],[15,18]].
def merge(intervals):
# STEP 1: Check empty and sort
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
# STEP 2: Initialize index
index = 0
# STEP 3: Iterate from second interval
for i in range(1, len(intervals)):
# STEP 4: Compare start of current with end of last merged
if intervals[i][0] <= intervals[index][1]:
# STEP 5: Merge intervals by updating end
intervals[index][1] = max(intervals[index][1], intervals[i][1])
else:
# STEP 8 & 11: No overlap, move index and copy current
index += 1
intervals[index] = intervals[i]
# STEP 12: Return merged intervals slice
return intervals[:index+1]
if __name__ == '__main__':
intervals = [[1,3],[2,6],[8,10],[15,18]]
print(merge(intervals))
📊
Merge Intervals - Watch the Algorithm Execute, Step by Step
Watching each pointer move and comparison helps you understand exactly how intervals are merged in-place without extra space.
Step 1/12
·Active fill★Answer cell
setup
0
1
2
3
setup
index
0
1
2
3
move_right
index
0
i
1
2
3
compare
index
0
i
1
2
3
insert
index
0
i
1
2
3
move_right
index
0
1
i
2
3
compare
index
0
1
i
2
3
insert
0
index
1
i
2
3
move_right
0
index
1
2
i
3
compare
0
index
1
2
i
3
insert
0
1
index
2
i
3
record
0
1
index
2
3
Result: [[1,6],[8,10],[15,18]]
Key Takeaways
✓ Sorting intervals by start time is essential to enable linear merging.
Without sorting, overlapping intervals could be scattered, making merging complex.
✓ The 'index' pointer tracks the last merged interval, allowing in-place merging without extra space.
This pointer movement shows how the algorithm compacts merged intervals at the front.
✓ Overlapping intervals are merged by extending the end time, while non-overlapping intervals advance the 'index' and are copied.
Seeing this decision visually clarifies when intervals combine versus when a new merged interval starts.
Practice
(1/5)
1. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?
easy
A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.
B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.
C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.
D. Use dynamic programming to store and compute overlapping intervals between the two lists.
Solution
Step 1: Understand problem constraints
Both lists are sorted and non-overlapping internally, so a linear scan is possible.
Step 2: Identify the optimal approach
Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.
Final Answer:
Option B -> Option B
Quick Check:
Two pointers avoid unnecessary comparisons and achieve linear time [OK]
Hint: Two pointers exploit sorted order for linear time [OK]
Common Mistakes:
Assuming brute force is acceptable
Thinking sorting combined lists is needed
Misapplying DP to interval intersection
2. You are given a list of intervals where each interval has a start and end time. Your goal is to select the maximum number of intervals such that none of the selected intervals overlap. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming that tries all subsets of intervals to find the maximum non-overlapping set.
B. Sort intervals by their start time and always pick the earliest starting interval first.
C. Sort intervals by their end time and greedily select intervals that start after the last selected interval ends.
D. Use a graph coloring algorithm to assign intervals to different colors ensuring no overlaps.
Solution
Step 1: Understand the problem goal
The problem requires selecting the maximum number of intervals with no overlaps.
Step 2: Identify the optimal greedy strategy
Sorting intervals by their end time and greedily picking intervals that start after the last selected interval ends ensures the maximum number of intervals are chosen.
Final Answer:
Option C -> Option C
Quick Check:
Greedy by earliest end time is a classic optimal approach [OK]
Hint: Sort by end time for max non-overlapping intervals [OK]
Common Mistakes:
Sorting by start time and picking earliest start first
Trying brute force DP without pruning
Using graph coloring which is unrelated here
3. Examine the following buggy code for the Meeting Rooms II problem. Which line contains the subtle bug that can cause incorrect room count?
medium
A. Line 3: Missing check for empty intervals list.
B. Line 9: Incorrect condition using >= instead of > for overlap.
C. Line 11: Using heappush without popping first.
D. Line 6: Intervals are not sorted before processing.
Solution
Step 1: Identify missing sorting.
Intervals must be sorted by start time before heap processing; missing this breaks heap logic.
Step 2: Confirm other lines.
Empty check is present; condition >= is correct for allowing room reuse; pushing after popping is correct.
Final Answer:
Option D -> Option D
Quick Check:
Without sorting, heap logic fails to track earliest ending meeting [OK]
Hint: Heap logic requires sorted intervals by start time [OK]
Common Mistakes:
Confusing overlap condition with <=
Forgetting to sort intervals
Misordering heap push/pop
4. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?
hard
A. Ignore zero-length intervals and ensure sorting places end events before start events at ties
B. Treat zero-length intervals as free time intervals
C. Sort events only by time, ignoring event type
D. Merge touching intervals as free time gaps
Solution
Step 1: Handle zero-length intervals
Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.
Step 2: Maintain correct sorting order
Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.
Final Answer:
Option A -> Option A
Quick Check:
Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]
Hint: Ignore zero-length intervals and sort end before start events [OK]
Common Mistakes:
Counting zero-length intervals as free time
Sorting start before end events
5. Suppose intervals can have negative values and zero length (start == end). Which modification to the optimal solution is necessary to correctly remove covered intervals?
hard
A. Change sorting to (start ascending, end ascending) to handle zero-length intervals correctly.
B. Use strict inequality 'if end > max_end' to avoid counting zero-length intervals as uncovered.
C. Switch to brute force nested loops to handle negative and zero-length intervals safely.
D. Keep sorting by (start ascending, end descending) and use 'if end >= max_end' to include zero-length coverage cases.
Solution
Step 1: Consider zero-length intervals
Zero-length intervals (start == end) require coverage detection to include intervals with equal ends.
Step 2: Adjust inequality and sorting
Sorting by start ascending and end descending remains correct; change condition to 'if end >= max_end' to count intervals not strictly greater but equal ends.
Final Answer:
Option D -> Option D
Quick Check:
Using >= includes zero-length coverage correctly without changing sorting [OK]
Hint: Use >= in condition to handle zero-length intervals [OK]
Common Mistakes:
Changing sorting breaks coverage detection
Using strict > misses zero-length coverage
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.