Overlap and merging

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

Merge extends the current region when the next start is within or touching it under the chosen union policy. Use max(end,next_end) so contained intervals cannot shrink the region.

Work through an example

[1,10) followed by [2,3) stays [1,10). The lab merges [1,3) and [2,6) to [1,6).

Time and space complexity

O(n) scan after sorting; O(n) output worst case.

Why it works

Output regions are ordered and disjoint, and their union equals all processed input.

Common mistakes

Assigning next_end directly shrinks containing intervals.
Overlap policy must match endpoint meaning.

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