Convert intervals/geometry into events, sort them, and sweep while tracking active state
Create start/end events (+1/−1 or custom), sort with careful tie-breaks, and maintain active structures during the sweep.
Use with intervals overlap, skyline, meeting rooms, or planar geometry intersections.
Convert to start/end events, sort with careful tie-breaks, and sweep while maintaining active counts or structures for overlaps/skylines.
# Sweep Line Template (Endpoint events)
def sweep_max_overlap(intervals):
events = [] # (x, delta)
for s,e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort(key=lambda x: (x[0], x[1]))
cur = best = 0
for _,d in events:
cur += d
best = max(best, cur)
return bestTreat starts as +1 and ends as −1; track running count
def max_overlap(intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1)) # treat end as leaving at time e
events.sort(key=lambda x: (x[0], x[1]))
cur = ans = 0
for _, d in events:
cur += d
ans = max(ans, cur)
return ansSort by x-coordinate; maintain active set by y-order
# Simplified skyline using events and max-heap
import heapq
def skyline(buildings):
events = []
for L, R, H in buildings:
events.append((L, -H, R)) # start
events.append((R, 0, 0)) # end
events.sort()
res = []
heap = [(0, float('inf'))] # (-height, end)
prev = 0
for x, negH, R in events:
while heap and heap[0][1] <= x: heapq.heappop(heap)
if negH: heapq.heappush(heap, (negH, R))
cur = -heap[0][0]
if not res or cur != prev:
res.append([x, cur])
prev = cur
return resGeneralized event counts with custom weights and tie rules
def timeline_concurrency(events):
# events: list of (time, delta)
events.sort(key=lambda x: (x[0], x[1]))
cur = best = 0
for _, d in events:
cur += d
best = max(best, cur)
return bestSorting events dominates; sweep is linear.
Active structures proportional to overlaps.