Sorting intervals

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

Sort by the dimension your reasoning uses. Start order supports scanning union regions; finish order supports maximum compatible count. Keep pair structure rather than sorting starts and ends independently unless doing a deliberate sweep.

Work through an example

For merging, [(8,10),(1,3),(2,6)] becomes [(1,3),(2,6),(8,10)]. Only the last output region can overlap the next sorted interval.

Time and space complexity

O(n log n) sort plus O(n) scan; copying avoids mutating caller order.

Why it works

All earlier output regions finish before the current region begins.

Common mistakes

Sorting by end for a start-based scan can break the invariant.
Losing start/end pairing changes intervals.

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