Intervals & sweep line

Process overlapping ranges by breaking them down into start and end events.

The idea

When dealing with many overlapping intervals (like finding the maximum number of concurrent meetings), comparing every interval to every other interval is O(N²).

The Sweep Line technique drops this to O(N log N). We break every interval into two events: a "Start" (+1 to active count) and an "End" (-1 to active count). We sort all events by time. By sweeping through them in order, we can track exactly how many intervals overlap at any given moment.

Active Overlaps: 0

Events sorted by time. Click Step.

How it works (Max Concurrent)

def maxConcurrent(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))  # +1 when starting
        events.append((end, -1))   # -1 when ending
        
    # Sort by time. If tie, process End (-1) before Start (+1)
    events.sort(key=lambda x: (x[0], x[1]))
    
    max_active = 0
    curr_active = 0
    
    for time, val in events:
        curr_active += val
        max_active = max(max_active, curr_active)
        
    return max_active