Insertion

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

Insert into an already sorted disjoint list by copying earlier intervals, merging overlaps with the new interval, then appending later intervals. The new interval's bounds may grow while scanning.

Work through an example

Insert [2,7) into [1,3),[6,9),[12,14): combine the first two into [1,9), then retain [12,14).

Time and space complexity

O(n) time/O(n) output; no new sort is needed if input preconditions hold.

Why it works

Earlier intervals are final; current insertion is the union of all overlapping consumed intervals.

Common mistakes

Stop comparing against the original end after it expands.
Unsorted or overlapping input needs normalization first.

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