Skip to main content

Merge Sweep

Trigger: you must use every interval. Sort by start, keep the last, extend it when the next one overlaps, otherwise start a new one, then read the answer off what you built. Not sure this is your page? Which question is it asking?

Most groups here run one loop, and differ in what they read off the result, where the intervals come from, or what lies between them. The exceptions say so in their intros, and the last group, two sorted lists, has no merge at all.

MNEMONIC

Combining? Look at the entrance. Meet each interval as it starts, stretch the last one or start a new one, then read the answer off what you built: a list, a flag, a number, the gaps, or the blocks.

The loop: merge and insert​

Merge overlapping intervals​

Sort by start, then walk the list against the last interval kept: if the two intersect, replace that last one with the pair merged; otherwise it is finished, so append the current interval as the new last. The two primitives from the index are the entire body of the loop.

def merge(intervals):
intervals.sort()
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
 
merged = []
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return merged

Starting from an empty merged and guarding with if merged and ... avoids seeding the list with intervals[0] as a special case, and intervals.sort() sorts by start already - tuples and lists compare element by element, so the start is the primary key for free.

Sorting by start is what makes this a single pass: once an interval is confirmed done (the next start is past its end), nothing later in the sorted list can ever reach back and overlap it again.

GOTCHAS3
Without sorting, merging is not just slower - it's a different, harder algorithm
Sort by start, not end - sorting by end can hide a merge
Losing the last interval

Insert a new interval​

A variant of merging: the list is already sorted and non-overlapping, and a single new interval needs to be dropped in - possibly merging with whatever it touches. Sorting the whole list again would work but throws away the fact that it was already sorted; a single linear scan in three phases does the same job without it.

def insert(intervals, new_interval):
result = []
i = 0
 
# Phase 1: intervals entirely before new_interval - copy through untouched
while i < len(intervals) and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
 
# Phase 2: intervals that overlap new_interval - absorb them into it
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)
 
# Phase 3: intervals entirely after new_interval - copy through untouched
while i < len(intervals):
result.append(intervals[i])
i += 1
 
return result
[1,2][3,5][6,7][9,10]new_interval = [4,8]absorbed into [3,8]
Phase 1 copies [1,2] through untouched; phase 2 absorbs [3,5] and [6,7] into the new interval, widening it to [3,8]; phase 3 copies [9,10] through untouched.

The two while conditions are asymmetric on purpose: phase 1 stops as soon as an interval's end reaches new_interval's start (it might still overlap), while phase 2 keeps going as long as an interval's start is within new_interval's current end (which grows as more intervals are absorbed) - that growing boundary is exactly why new_interval[1] has to be re-checked with max() on every absorption, not just the first.

The merged list​

The merged ranges themselves are the answer. This is the loop worth memorising; the groups below change only what they read off it, where the intervals come from, or what lies between them.

56. Merge Intervals​

56

Merge Intervals

LeetCode
Medium

Sort by Start, Merge in Place

FIG. 56 MERGE INTERVALS● INTERACTIVE
visualization loads as you reach it
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
 
merged = []
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return merged
top ↑

228. Summary Ranges​

228

Summary Ranges

LeetCode
Easy

Merge Consecutive Runs

FIG. 228 SUMMARY RANGES TWO PASS● INTERACTIVE
visualization loads as you reach it
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
 
merged = []
for i in nums:
inter = [i - 1, i]
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append([i, i])
res = []
for i, j in merged:
if i == j:
res.append(str(i))
else:
res.append(f"{i}->{j}")
return res
top ↑

57. Insert Interval​

57

Insert Interval

LeetCode
Medium

One-Pass Merge

FIG. 57 INSERT INTERVAL● INTERACTIVE
visualization loads as you reach it
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
isInGapStrictly = lambda left, right, a: a[0] > left[1] and a[1] < right[0]
 
merged = [[-1, -1]]
for inter in intervals:
if doesIntersect(newInterval, inter):
inter = getMerged(newInterval, inter)
elif isInGapStrictly(merged[-1], inter, newInterval):
merged.append(newInterval)
 
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
last_inter = intervals[-1] if intervals else [-1, -1]
if isInGapStrictly(last_inter, [float("inf"), float("inf")], newInterval):
merged.append(newInterval)
return merged[1:]
top ↑

Does anything overlap​

Keep a boolean, not the list. Merge everything and compare the count, or bail out the first time the sweep would merge. With only two intervals the sweep collapses to a single overlap test. Mind the endpoint rule: Meeting Rooms treats a shared endpoint as no conflict, Determine if Two Events Have Conflict treats it as one.

252. Meeting Rooms​

252

Meeting Rooms

LeetCode
Easy

Merge and Compare Lengths

FIG. 252 MEETING ROOMS MERGE● INTERACTIVE
visualization loads as you reach it
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersectStrictly = lambda a, b: (a[1] > b[0] and b[1] > a[0])
 
merged = []
for inter in intervals:
if merged and doesIntersectStrictly(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return len(merged) == len(intervals)
top ↑

2446. Determine if Two Events Have Conflict​

2446

Determine if Two Events Have Conflict

LeetCode
Easy

Normalize, Then Shared Overlap Test

FIG. 2446 DETERMINE IF TWO EVENTS HAVE CONFLICT● INTERACTIVE
visualization loads as you reach it
class Solution:
def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
def toMinutes(hhmm):
hh, mm = map(int, hhmm.split(":"))
return hh * 60 + mm
 
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
 
a = list(map(toMinutes, event1))
b = list(map(toMinutes, event2))
return doesIntersect(a, b)
top ↑

How much is covered​

Return a number or a flag, not a list. The union's total length, how many integer points it contains, how many disjoint groups it splits into, or whether it swallows a given target range. Each needs only the last merged interval and a running answer. Remove Covered Intervals is the odd one: it tests containment instead of overlap and counts the intervals that no earlier one swallows.

2580. Count Ways to Group Overlapping Ranges​

2580

Count Ways to Group Overlapping Ranges

LeetCode
Medium

Merge, Then Count the List

FIG. 2580 COUNT WAYS TO GROUP OVERLAPPING RANGES● INTERACTIVE
visualization loads as you reach it
class Solution:
def countWays(self, ranges: List[List[int]]) -> int:
ranges.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
merged = []
for inter in ranges:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
x = len(merged)
return (2**x) % ((10**9) + 7)
top ↑

2848. Points That Intersect With Cars​

2848

Points That Intersect With Cars

LeetCode
Easy

Merge, Then Sum

FIG. 2848 POINTS THAT INTERSECT WITH CARS MERGE THEN SUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def numberOfPoints(self, nums: List[List[int]]) -> int:
nums.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
 
merged = []
for inter in nums:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
res = 0
for i, j in merged:
res += j - i + 1
return res
top ↑

495. Teemo Attacking​

495

Teemo Attacking

LeetCode
Easy

Merge, Then Sum

FIG. 495 TEEMO ATTACKING MERGE THEN SUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
intervalSize = lambda a: a[1] - a[0] + 1
 
merged = []
ans = 0
for i in timeSeries:
inter = [i, i + duration - 1]
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
for inter in merged:
ans += intervalSize(inter)
return ans
top ↑

1893. Check if All the Integers in a Range Are Covered​

1893

Check if All the Integers in a Range Are Covered

LeetCode
Easy

Merge, Then Check Containment

FIG. 1893 CHECK IF ALL THE INTEGERS IN A RANGE ARE COVERED MERGE THEN CHECK● INTERACTIVE
visualization loads as you reach it
class Solution:
def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
ranges.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
merged = []
 
for inter in ranges:
inter = [inter[0] - 1, inter[1]]
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
for inter in merged:
i, j = inter[0] + 1, inter[1]
if left >= i or right <= j:
if left >= i and right <= j:
return True
return False
top ↑

1288. Remove Covered Intervals​

1288

Remove Covered Intervals

LeetCode
Medium

Track Kept Intervals

FIG. 1288 REMOVE COVERED INTERVALS● INTERACTIVE
visualization loads as you reach it
class Solution:
def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda i: (i[0], -i[1]))
count = 0
doesContain = lambda a, b: (a[0] <= b[0] and b[1] <= a[1])
merged = []
for inter in intervals:
if merged and doesContain(merged[-1], inter):
...
else:
merged.append(inter)
return len(merged)
top ↑

The gaps​

Report the complement. Merge as usual, but report or total the gaps between consecutive merged intervals rather than the intervals themselves. Most also need the two boundary gaps, one before the first interval and one after the last, clipped to the outer range the problem gives; Employee Free Time has no outer range, so it reports only the inner gaps.

3169. Count Days Without Meetings​

3169

Count Days Without Meetings

LeetCode
Medium

Merge, Then Sum

FIG. 3169 COUNT DAYS WITHOUT MEETINGS MERGE THEN SUM● INTERACTIVE
visualization loads as you reach it
class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
meetings.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
getGap = lambda a, b: (max(a[0], b[0]) - min(a[1], b[1]) - 1)
 
merged = [[0, 0]]
for inter in meetings:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
merged.append([days + 1, days + 1])
no_meeting_days = 0
for i in range(len(merged) - 1):
no_meeting_days += getGap(merged[i], merged[i + 1])
return no_meeting_days
top ↑

2655. Find Maximal Uncovered Ranges​

2655

Find Maximal Uncovered Ranges

LeetCode
Medium

Merge, Then Find Gaps

FIG. FIND MAXIMAL UNCOVERED RANGES MERGE THEN FIND GAPS● INTERACTIVE
visualization loads as you reach it
class Solution:
def findMaximalUncoveredRanges(self, n: int, ranges: List[List[int]]) -> List[List[int]]:
ranges.sort()
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
merged = [[-1, -1]]
 
for inter in ranges:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
merged.append([n, n])
ans = []
for i in range(len(merged) - 1):
i, j = merged[i][1] + 1, merged[i + 1][0] - 1
if i <= j:
ans.append([i, j])
return ans
top ↑

163. Missing Ranges​

163

Missing Ranges

LeetCode
Easy

Merge, Then Find Gaps

FIG. 163 MISSING RANGES MERGE THEN FIND GAPS● INTERACTIVE
visualization loads as you reach it
class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[List[int]]:
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
merged = [[lower - 1, lower - 1]]
for n in nums:
inter = [n - 1, n]
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
merged.append([upper, upper])
# print(merged)
ans = []
for i in range(len(merged) - 1):
i, j = merged[i][1] + 1, merged[i + 1][0]
if i <= j:
ans.append([i, j])
return ans
top ↑

759. Employee Free Time​

759

Employee Free Time

LeetCode
Hard

Merge, Then Find Gaps

FIG. EMPLOYEE FREE TIME MERGE THEN FIND GAPS● INTERACTIVE
visualization loads as you reach it
class Solution:
def employeeFreeTime(self, schedule: "[[Interval]]") -> "[Interval]":
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
getGapInterval = lambda a, b: Interval(min(a[1], b[1]), max(a[0], b[0]))
 
busy = sorted((sch.start, sch.end) for emp in schedule for sch in emp)
merged = []
for inter in busy:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
ans = []
for i in range(len(merged) - 1):
ans.append(getGapInterval(merged[i], merged[i + 1]))
return ans
top ↑

3964. Minimum Lights to Illuminate a Road​

3964

Minimum Lights to Illuminate a Road

LeetCode
Medium

Merge Illuminated Spans, Fill Gaps

FIG. 3964 MINIMUM LIGHTS TO ILLUMINATE A ROAD● INTERACTIVE
visualization loads as you reach it
class Solution:
def minLights(self, lights: list[int]) -> int:
intervals = []
n = len(lights)
for i, v in enumerate(lights):
if v:
intervals.append([max(0, i - v), min(n - 1, i + v)])
intervals.append([n, n])
intervals.sort()
 
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
getGap = lambda a, b: max(a[0], b[0]) - min(a[1], b[1])
 
merged = [[-1, -1]]
ans = 0
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
gap = getGap(merged[-1], inter) - 1
ans += (gap + 2) // 3
merged.append(inter)
return ans
top ↑

Cutting a sequence into pieces​

Build the intervals first; no sort of the intervals themselves. Each value (or letter) claims the stretch of indices it must stay inside: from its first to its last occurrence, or from where it sits to where it has to end up. Merging those stretches leaves the smallest blocks the sequence can be cut into, and you build them in one pass over the input, so the intervals themselves are never sorted. The answer is read off the blocks: their sizes, their count, or the number of ways to cut between them.

763. Partition Labels​

763

Partition Labels

LeetCode
Medium

Merge Overlapping Intervals

FIG. 763 PARTITION LABELS● INTERACTIVE
visualization loads as you reach it
class Solution:
def partitionLabels(self, s: str) -> list[int]:
hm = {}
for idx, char in enumerate(s):
if char not in hm:
hm[char] = [idx, idx]
else:
hm[char][1] = idx
 
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
getSize = lambda a: a[1] - a[0] + 1
merged = []
ans = []
for inter in hm.values():
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
ans[-1] = getSize(merged[-1])
else:
merged.append(inter)
ans.append(getSize(merged[-1]))
return ans
top ↑

2963. Count the Number of Good Partitions​

2963

Count the Number of Good Partitions

LeetCode
Hard

Merge, Then Count the List

FIG. 2963 COUNT THE NUMBER OF GOOD PARTITIONS● INTERACTIVE
visualization loads as you reach it
class Solution:
def numberOfGoodPartitions(self, nums: List[int]) -> int:
hm = {}
for idx, num in enumerate(nums):
if num not in hm:
hm[num] = [idx, idx]
else:
hm[num][1] = idx
 
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
merged = []
for inter in hm.values():
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return pow(2, len(merged) - 1, 10**9 + 7)
top ↑

769. Max Chunks To Make Sorted​

769

Max Chunks To Make Sorted

LeetCode
Medium

Merge, Then Count the List

FIG. 769 MAX CHUNKS TO MAKE SORTED● INTERACTIVE
visualization loads as you reach it
class Solution:
def maxChunksToSorted(self, arr: list[int]) -> int:
intervals = []
for idx, num in enumerate(arr):
intervals.append((min(idx, num), max(idx, num)))
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
 
merged = []
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return len(merged)
top ↑

768. Max Chunks To Make Sorted II​

768

Max Chunks To Make Sorted II

LeetCode
Hard

Merge, Then Count the List

class Solution:
def maxChunksToSorted(self, arr: list[int]) -> int:
sorted_arr = sorted(arr)
hm = {}
intervals = []
for idx, num in enumerate(arr):
if num not in hm:
hm[num] = bisect.bisect_left(sorted_arr, num) - 1
hm[num] += 1
intervals.append((min(hm[num], idx), max(hm[num], idx)))
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
doesIntersect = lambda a, b: a[1] >= b[0] and b[1] >= a[0]
merged = []
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
merged[-1] = getMerged(merged[-1], inter)
else:
merged.append(inter)
return len(merged)
top ↑

Two sorted lists​

No merge: two pointers, advance the earlier end. Both lists are already sorted and internally disjoint, so emit the shared stretch of the current pair if there is one, then advance whichever interval ends first, because it can never intersect anything later.

986. Interval List Intersections​

986

Interval List Intersections

LeetCode
Medium

Two-Pointer Merge

FIG. 986 INTERVAL LIST INTERSECTIONS● INTERACTIVE
visualization loads as you reach it
class Solution:
def intervalIntersection(
self, firstList: List[List[int]], secondList: List[List[int]]
) -> List[List[int]]:
common = []
getIntersection = lambda a, b: (max(a[0], b[0]), min(a[1], b[1]))
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
i = j = 0
while i < len(firstList) and j < len(secondList):
a, b = firstList[i], secondList[j]
if doesIntersect(a, b):
inter = getIntersection(a, b)
common.append(inter)
if a[1] < b[1]:
i += 1
else:
j += 1
return common
top ↑
On this page