Skip to main content

Problems

Start at the top. The first group is the merge sweep itself - sort by start, extend the last interval when the next one touches it, append otherwise - and every group after it is that identical loop with a different thing measured at the end. Learn the sweep once and the rest of the page is deciding what to do with merged.

Merge overlapping​

The merged list itself is the answer, so this is the loop worth memorising. Everything below reuses it verbatim.

56. Merge Intervals​

Medium·
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

57. Insert Interval​

Medium·
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:]

228. Summary Ranges​

Easy·
3 Approaches
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

352. Data Stream as Disjoint Intervals​

Hard·
3 Approaches
FIG. 352 DATA STREAM AS DISJOINT INTERVALS● INTERACTIVE
visualization loads as you reach it
class SummaryRanges:
 
def __init__(self):
self.intervals = []
 
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
 
def addNum(self, value: int) -> None:
self.intervals.append((value, value + 1))
self.intervals = self.merge(self.intervals)
 
def getIntervals(self) -> list[list[int]]:
return [[i, j - 1] for i, j in self.intervals]
 
 
# Your SummaryRanges object will be instantiated and called as such:
# obj = SummaryRanges()
# obj.addNum(value)
# param_2 = obj.getIntervals()

Do any overlap​

Now throw the list away and keep a boolean. Because merged only ever grows when the next interval doesn't touch the last one, "did anything overlap" is just "did the merged list come out shorter than the input" - which means you can answer it without building the list at all, bailing out the first time the sweep would have merged. With only two intervals the sweep collapses to a single disjoint test.

2446. Determine if Two Events Have Conflict​

Easy·
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)

252. Meeting Rooms​

Easy·
3 Approaches
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)

729. My Calendar I​

Medium·
FIG. 729 MY CALENDAR I● INTERACTIVE
visualization loads as you reach it
class MyCalendar:
 
def __init__(self):
self.intervals = [[-1, -1]]
 
def book(self, startTime: int, endTime: int) -> bool:
doesIntersectStrictly = lambda a, b: (a[1] > b[0] and b[1] > a[0])
isInGap = lambda left, right, a: a[0] >= left[1] and a[1] <= right[0]
newInterval = [startTime, endTime]
 
for i in range(1, len(self.intervals)):
if isInGap(self.intervals[i - 1], self.intervals[i], newInterval):
self.intervals.insert(i, newInterval)
return True
if doesIntersectStrictly(self.intervals[i], newInterval):
return False
self.intervals.append(newInterval)
return True
 
 
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

Count the merged groups​

A step further than a plain overlap flag: instead of stopping at the first merge, run the whole sweep and count how many disjoint groups merged ends up with. Each group is independent of every other, so a question like "how many ways can you 2-color the ranges so no overlapping pair shares a color" is just 2 raised to that group count.

2580. Count Ways to Group Overlapping Ranges​

Medium·
2 Approaches
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)

How much is covered​

Same idea, but the measurement is a number rather than a flag: the union's total length, how many integer points it contains, or whether it swallows a given target range. As above, nothing is returned, so each of these has a version that never allocates a list and just accumulates while merging.

495. Teemo Attacking​

Easy·
3 Approaches
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

2848. Points That Intersect With Cars​

Easy·
3 Approaches
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

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

Easy·
5 Approaches
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

452. Minimum Number of Arrows to Burst Balloons​

Medium·
2 Approaches
FIG. 452 MINIMUM NUMBER OF ARROWS TO BURST BALLOONS● INTERACTIVE
visualization loads as you reach it
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
points.sort()
doesIntersect = lambda a, b: (a[1] >= b[0] and b[1] >= a[0])
getIntersection = lambda a, b: (max(a[0], b[0]), min(a[1], b[1]))
 
intersection = []
for inter in points:
if intersection and doesIntersect(intersection[-1], inter):
intersection[-1] = getIntersection(intersection[-1], inter)
else:
intersection.append(inter)
return len(intersection)

435. Non-overlapping Intervals​

Medium·
2 Approaches
FIG. 435 NON OVERLAPPING INTERVALS● INTERACTIVE
visualization loads as you reach it
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
doesIntersectStrictly = lambda a, b: (a[1] > b[0] and b[1] > a[0])
getIntersection = lambda a, b: (max(a[0], b[0]), min(a[1], b[1]))
 
intersection = []
count = 0
for inter in intervals:
if intersection and doesIntersectStrictly(intersection[-1], inter):
intersection[-1] = getIntersection(intersection[-1], inter)
count += 1
else:
intersection.append(inter)
return count

1288. Remove Covered Intervals​

Medium·
2 Approaches
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)

What is not covered​

The complement. Merge as usual, but report the gaps between consecutive merged intervals rather than the intervals themselves. The only real work beyond the previous group is the two boundary gaps: one before the first interval and one after the last, both clipped to whatever outer range the problem gives you.

163. Missing Ranges​

Easy·
3 Approaches
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

2655. Find Maximal Uncovered Ranges​

Medium·
3 Approaches
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

3169. Count Days Without Meetings​

Medium·
3 Approaches
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

3964. Minimum Lights to Illuminate a Road​

Medium·
4 Approaches
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

759. Employee Free Time​

Hard·
4 Approaches
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

Peak concurrent overlap​

Not merge-based at all: turning each interval into a +1 at its start and a -1 at its end and sweeping the sorted events gives a running count of how many intervals are active at any instant. The maximum that count ever reaches is the answer whenever the question is "how many things overlap at once", rather than "do any overlap" or "what's covered".

253. Meeting Rooms II​

Medium·
3 Approaches
FIG. 253 MEETING ROOMS II● INTERACTIVE
visualization loads as you reach it
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
def streamEvents(intervals):
events = []
for start, end in intervals:
events.extend([(start, 1), (end, -1)])
return sorted(events)
 
active = maxi = 0
for point, curr in streamEvents(intervals):
active += curr
maxi = max(maxi, active)
return maxi

1094. Car Pooling​

Medium·
3 Approaches
FIG. 1094 CAR POOLING SWEEP● INTERACTIVE
visualization loads as you reach it
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
def streamEvents(intervals):
events = []
for num, start, end in intervals:
events.extend([(start, num), (end, -num)])
return sorted(events)
 
active = 0
for point, curr in streamEvents(trips):
active += curr
if active > capacity:
return False
return True

731. My Calendar II​

Medium·
2 Approaches
FIG. 731 MY CALENDAR II● INTERACTIVE
visualization loads as you reach it
import sortedcontainers
 
 
class MyCalendarTwo:
 
def __init__(self):
self.line = sortedcontainers.SortedDict()
 
def book(self, startTime: int, endTime: int) -> bool:
self.line[startTime] = self.line.get(startTime, 0) + 1
self.line[endTime] = self.line.get(endTime, 0) - 1
active = 0
for point, curr in self.line.items():
active += curr
if active > 2:
self.line[startTime] -= 1
self.line[endTime] += 1
return False
return True
 
 
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(startTime,endTime)

732. My Calendar III​

Hard·
FIG. 732 MY CALENDAR III● INTERACTIVE
visualization loads as you reach it
from sortedcontainers import SortedDict
 
 
class MyCalendarThree:
 
def __init__(self):
self.line = SortedDict()
 
def book(self, startTime: int, endTime: int) -> int:
self.line[startTime] = self.line.get(startTime, 0) + 1
self.line[endTime] = self.line.get(endTime, 0) - 1
active = maxi = 0
for point, curr in self.line.items():
active += curr
maxi = max(maxi, active)
return maxi
 
 
# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(startTime,endTime)

2276. Count Integers in Intervals​

Hard·
2 Approaches
FIG. 2276 COUNT INTEGERS IN INTERVALS MERGE● INTERACTIVE
visualization loads as you reach it
class CountIntervals:
def __init__(self):
self.intervals = []
self.len = 0
 
def merge(self, intervals: List[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])
 
merged = []
self.len = 0
for inter in intervals:
if merged and doesIntersect(merged[-1], inter):
self.len -= merged[-1][1] - merged[-1][0] + 1
merged[-1] = getMerged(merged[-1], inter)
self.len += merged[-1][1] - merged[-1][0] + 1
else:
self.len += inter[1] - inter[0] + 1
merged.append(inter)
return merged
 
def add(self, left: int, right: int) -> None:
idx = bisect.bisect_left(self.intervals, left, key=lambda i: i[0])
self.intervals.insert(idx, (left, right))
self.intervals = self.merge(self.intervals)
 
def count(self) -> int:
return self.len

2406. Divide Intervals Into Minimum Number of Groups​

Medium·
2 Approaches
FIG. 2406 DIVIDE INTERVALS SWEEP● INTERACTIVE
visualization loads as you reach it
class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
def streamEvents(intervals):
line = []
for a, b in intervals:
line.extend([[a, 1], [b + 1, -1]])
return sorted(line)
 
active = maxi = 0
for point, curr in streamEvents(intervals):
active += curr
maxi = max(maxi, active)
return maxi

1419. Minimum Number of Frogs Croaking​

Medium·
2 Approaches
FIG. 1419 MIN FROGS BUCKETS● INTERACTIVE
visualization loads as you reach it
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
buckets = [0] * (len(croakOfFrogs))
counter = collections.defaultdict(int)
croak = "croak"
maxi = active = 0
for idx, char in enumerate(croakOfFrogs):
if char == "c":
buckets[idx] += 1
elif char == "k":
buckets[idx] -= 1
active += buckets[idx]
counter[char] += 1
maxi = max(maxi, active)
if not (counter["c"] >= counter["r"] >= counter["o"] >= counter["a"] >= counter["k"]):
return -1
return maxi if counter["c"] == counter["k"] else -1

1854. Maximum Population Year​

Easy·
2 Approaches
FIG. 1854 MAXIMUM POPULATION YEAR SWEEP● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
def streamEvents(intervals):
line = []
for start, end in intervals:
line.extend([[start, 1], [end, -1]])
return sorted(line, key=lambda i: i)
 
maxi = [-1, 1930]
active = 0
for point, curr in streamEvents(logs):
active += curr
# print(point, curr)
if maxi[0] < active:
maxi = (active, point)
return maxi[1]

370. Range Addition​

Medium·
2 Approaches
FIG. 370 RANGE ADDITION SWEEP● INTERACTIVE
visualization loads as you reach it
class Solution:
def getModifiedArray(self, length: int, updates: List[List[int]]) -> List[int]:
def streamEvents(intervals):
line = []
for start, end, weight in intervals:
line.extend([[start, weight], [end + 1, -weight]])
return sorted(line)
 
res = [0] * (length + 1)
prev = None
active = 0
for point, curr in streamEvents(updates):
start = point if prev is None else prev
for i in range(start, point + 1):
res[i] = active
active += curr
res[point] = active
prev = point
return res[:length]

2381. Shifting Letters II​

Medium·
FIG. 2381 SHIFTING LETTERS II● INTERACTIVE
visualization loads as you reach it
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
buckets = [0] * (len(s) + 1)
for start, end, direction in shifts:
direction = -1 if direction == 0 else 1
buckets[start] += direction
buckets[end + 1] -= direction
ans = []
alphabets = "abcdefghijklmnopqrstuvwxyz"
alphabet_map = {j: i for i, j in enumerate(alphabets)}
active = 0
for point, curr in enumerate(buckets[:-1]):
active += curr
char = alphabets[(alphabet_map[s[point]] + active) % 26]
ans.append(char)
return "".join(ans)

2237. Count Positions on Street With Required Brightness​

Medium·
FIG. 2237 COUNT POSITIONS ON STREET WITH REQUIRED BRIGHTNESS● INTERACTIVE
visualization loads as you reach it
class Solution:
def meetRequirement(self, n: int, lights: List[List[int]], requirement: List[int]) -> int:
buckets = [0] * (n + 2)
for center, rang in lights:
start = max(0, center - rang)
end = min(n - 1, center + rang)
buckets[start] += 1
buckets[end + 1] -= 1
active = 0
count = 0
for point, curr in enumerate(buckets[:-2]):
active += curr
if active >= requirement[point]:
count += 1
return count

2779. Maximum Beauty of an Array After Applying Operation​

Medium·
2 Approaches · 2 patterns
FIG. MAXIMUM BEAUTY OF AN ARRAY AFTER APPLYING OPERATION● INTERACTIVE
visualization loads as you reach it
class Solution:
def maximumBeauty(self, nums: List[int], k: int) -> int:
def streamEvents(interval):
line = []
for i in interval:
line.extend([[i - k, 1], [i + k + 1, -1]])
return sorted(line)
 
active = 0
maxi = 0
for point, curr in streamEvents(nums):
active += curr
maxi = max(maxi, active)
return maxi

Weighted concurrent sum​

Same +1/-1 sweep, but each event carries a weight instead of a flat unit, so the running total is a sum rather than a count - and every distinct stretch between consecutive event points, not just the peak, is reported alongside whatever that sum was during it.

1943. Describe the Painting​

Medium·
FIG. DESCRIBE THE PAINTING● INTERACTIVE
visualization loads as you reach it
class Solution:
def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
def streamEvents(intervals):
line = []
for start, end, weight in intervals:
line.extend([[start, weight], [end, -weight]])
return sorted(line)
 
ans = []
active = 0
prev = None
for point, curr in streamEvents(segments):
if prev and point != prev and active:
ans.append([prev, point, active])
prev = point
active += curr
return ans

Concurrent count at query points​

Same +1/-1 sweep as above, but instead of the single overall peak, the running count is needed at several specific instants - one per query point. Sort the queries too, and drain every query that falls before the current event point as the sweep passes it, recording whatever active is at that moment.

2251. Number of Flowers in Full Bloom​

Hard·
FIG. 2251 NUMBER OF FLOWERS IN FULL BLOOM● INTERACTIVE
visualization loads as you reach it
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
def streamEvents(interval):
events = []
for start, end in flowers:
events.extend([[start, 1], [end + 1, -1]])
return sorted(events)
 
people_sorted = sorted(people)
active = 0
prev = 0
ans = {}
finder = 0
for point, curr in streamEvents(flowers):
while finder < len(people_sorted) and prev <= people_sorted[finder] < point:
ans[people_sorted[finder]] = active
finder += 1
active += curr
prev = point
return [ans.get(i, 0) for i in people]

Two sorted lists​

The one group that abandons the sweep. When the input arrives as two already-sorted lists there is nothing to sort and nothing to merge - you walk both with two pointers, emit the shared stretch of the current pair if there is one, and advance whichever interval ends first, because it can never intersect anything later.

986. Interval List Intersections​

Medium·
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 = []
getMerged = lambda a, b: (min(a[0], b[0]), max(a[1], b[1]))
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