Endpoint conventions

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

Closed [a,b] includes both ends; half-open [a,b) excludes b. An empty half-open interval has a=b. Decide whether touching should merge, conflict, or reuse a resource based on the task.

Work through an example

[1,2) and [2,3) share no points, so one room suffices. Their union is [1,3), so a union merger may still combine them.

Time and space complexity

Endpoint tests O(1); n intervals O(n) storage before any sorting.

Why it works

Every overlap comparison follows one consistent endpoint policy.

Common mistakes

<= versus < changes touching behavior.
A zero-duration interval is empty under half-open semantics.

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