Sweep-line events

What is an interval?

An interval describes a continuous range using a start and an end. Endpoint rules determine whether the start and end are included. Two intervals overlap when they share a point under those rules. Sorting intervals often makes it easier to merge ranges or schedule events.

Example: The closed intervals [1, 4] and [3, 6] overlap and merge into [1, 6]. For half-open intervals, [1, 4) excludes 4, so [1, 4) and [4, 6) do not overlap.

Helpful before this chapter

If these ideas are new, begin with:

Sorting and selection

Understand the idea

A sweep replaces each interval with boundary events and scans coordinates in order. Active count measures concurrency; coverage length also needs the distance to the previous coordinate while count>0.

Work through an example

For [1,4),[2,3),[3,5), ends at 3 are processed before starts at 3. Peak active count is 2, not 3.

Time and space complexity

O(n log n) sort/O(n) events; coordinate compression supports large sparse coordinates.

Why it works

Between consecutive event coordinates, active count is constant.

Common mistakes

Equal-coordinate ordering follows endpoint semantics.
Counting active intervals differs from counting covered integer points.

Chapter lab · Python implementation

An interval is meaningful only with endpoint conventions. We use half-open [start,end) for scheduling; the merge lab merges touching intervals because their union is contiguous. That touching rule is a deliberate merge policy, while active-room counting treats an end at t as finished before a start at t.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def merge(intervals):
    output=[]
    for start,end in sorted(intervals):
        if start>end: raise ValueError('invalid interval')
        if not output or start>output[-1][1]:
            output.append([start,end])
        else:
            output[-1][1]=max(output[-1][1],end)
    return output

def rooms(intervals):
    events=[]
    for start,end in intervals:
        if start>end: raise ValueError('invalid interval')
        if start==end: continue
        events.extend([(start,1),(end,-1)])
    active=best=0
    for time,change in sorted(events):
        active+=change; best=max(best,active)
    return best

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert merge([(1,3),(2,6),(8,10),(10,12)])==[[1,6],[8,12]]
assert merge([])==[]
assert rooms([(1,4),(2,3),(3,5)])==2
assert rooms([(1,2),(2,3)])==1
assert rooms([(2,2)])==0

CHECK YOUR UNDERSTANDING