17.10 Interval Geometry

Problem

You need to solve geometric problems that can be reduced to one-dimensional intervals.

Many two-dimensional problems contain an interval subproblem. Rectangle union, line sweep algorithms, calendar conflicts, range coverage, collision detection, and spatial indexing all require operations such as:

insert an interval
delete an interval
merge overlapping intervals
measure total covered length
find whether a point is covered
find maximum overlap

Getting interval geometry right is important because sweep-line algorithms frequently delegate their active-state logic to interval routines.

Solution

Represent each interval with a start and end coordinate.

For most algorithms, normalize the interval so that:

start <= end

A simple implementation:

from dataclasses import dataclass

@dataclass(frozen=True)
class Interval:
    start: float
    end: float

    def __post_init__(self):
        if self.start > self.end:
            raise ValueError("interval start must be <= end")

For integer coordinates, the same structure works with int.

The main design decision is whether intervals are closed, open, or half-open.

For algorithmic work, half-open intervals are often the cleanest:

[start, end)

This means start is included and end is excluded.

Half-open intervals avoid double-counting boundaries when adjacent intervals touch.

[1, 3) and [3, 5)

cover length:

4

not:

5

and not an overlapping point at 3.

Merging Intervals

Given intervals:

[1, 4)
[2, 6)
[8, 10)
[9, 12)

the merged result is:

[1, 6)
[8, 12)

Implementation:

def merge_intervals(intervals):
    if not intervals:
        return []

    intervals = sorted(intervals, key=lambda interval: interval.start)

    merged = [intervals[0]]

    for current in intervals[1:]:
        previous = merged[-1]

        if current.start <= previous.end:
            merged[-1] = Interval(
                previous.start,
                max(previous.end, current.end)
            )
        else:
            merged.append(current)

    return merged

For half-open intervals, decide whether touching intervals should merge.

If [1, 3) and [3, 5) should remain separate, use:

if current.start < previous.end:
    ...

If they should merge into [1, 5), use:

if current.start <= previous.end:
    ...

This choice depends on the problem.

Total Covered Length

After merging intervals, total coverage is straightforward:

def covered_length(intervals):
    merged = merge_intervals(intervals)

    total = 0

    for interval in merged:
        total += interval.end - interval.start

    return total

Example:

[1, 4)
[2, 6)
[8, 10)
[9, 12)

Merged:

[1, 6)
[8, 12)

Covered length:

(6 - 1) + (12 - 8) = 9

This routine appears directly inside rectangle-union and sweep-line area algorithms.

Point Coverage

To test whether a point lies inside any interval, first merge the intervals, then binary search.

from bisect import bisect_right

def contains_point(intervals, x):
    merged = merge_intervals(intervals)
    starts = [interval.start for interval in merged]

    index = bisect_right(starts, x) - 1

    if index < 0:
        return False

    interval = merged[index]

    return interval.start <= x < interval.end

For many queries, merge once and reuse the result.

class IntervalSet:
    def __init__(self, intervals):
        self.intervals = merge_intervals(intervals)
        self.starts = [
            interval.start
            for interval in self.intervals
        ]

    def contains(self, x):
        index = bisect_right(self.starts, x) - 1

        if index < 0:
            return False

        interval = self.intervals[index]

        return interval.start <= x < interval.end

This gives:

O(log n)

query time after preprocessing.

Maximum Overlap

Given intervals, find the largest number of intervals covering the same point.

Use events:

start event: +1
end event:   -1

Implementation:

def maximum_overlap(intervals):
    events = []

    for interval in intervals:
        events.append((interval.start, 1))
        events.append((interval.end, -1))

    events.sort(key=lambda event: (event[0], event[1]))

    active = 0
    best = 0

    for _, delta in events:
        active += delta
        best = max(best, active)

    return best

With half-open intervals, end events should be processed before start events at the same coordinate.

That is why sorting by:

(event[0], event[1])

works: -1 comes before +1.

Example:

[1, 3)
[3, 5)

The first interval ends exactly when the second starts. They do not overlap.

Finding Overlap Between Two Interval Sets

Given two sorted, non-overlapping interval lists, find all intersections.

def intersect_interval_sets(a, b):
    i = 0
    j = 0
    result = []

    while i < len(a) and j < len(b):
        start = max(a[i].start, b[j].start)
        end = min(a[i].end, b[j].end)

        if start < end:
            result.append(Interval(start, end))

        if a[i].end < b[j].end:
            i += 1
        else:
            j += 1

    return result

This is a two-pointer scan.

Time complexity:

O(n + m)

where n and m are the sizes of the two interval sets.

Rectangle Projection

A rectangle can be projected onto the x-axis and y-axis.

For a rectangle:

left, bottom, right, top

the projections are:

x interval: [left, right)
y interval: [bottom, top)

Two axis-aligned rectangles overlap if both projections overlap.

@dataclass(frozen=True)
class Rectangle:
    left: float
    bottom: float
    right: float
    top: float

def intervals_overlap(a, b):
    return a.start < b.end and b.start < a.end

def rectangles_overlap(a, b):
    ax = Interval(a.left, a.right)
    ay = Interval(a.bottom, a.top)

    bx = Interval(b.left, b.right)
    by = Interval(b.bottom, b.top)

    return intervals_overlap(ax, bx) and intervals_overlap(ay, by)

This projection idea is one of the simplest examples of interval geometry inside two-dimensional geometry.

Dynamic Interval Coverage

Some sweep-line algorithms require intervals to be inserted and deleted while repeatedly asking for total covered length.

A simple list-based implementation is often enough for small inputs:

class DynamicIntervalSet:
    def __init__(self):
        self.intervals = []

    def add(self, interval):
        self.intervals.append(interval)

    def remove(self, interval):
        self.intervals.remove(interval)

    def covered_length(self):
        return covered_length(self.intervals)

This is easy to reason about, but inefficient.

For large inputs, use a segment tree or balanced interval tree. Rectangle-union algorithms commonly use coordinate compression plus a segment tree to maintain covered y-length while sweeping across x-events.

Coordinate Compression

When intervals use many large coordinates but only endpoints matter, compress coordinates.

Example endpoints:

1000000000
1000000050
1000000100

can become:

0
1
2

while preserving order.

def compress_coordinates(values):
    sorted_values = sorted(set(values))

    index = {
        value: i
        for i, value in enumerate(sorted_values)
    }

    return index, sorted_values

Coordinate compression is especially useful when building segment trees over interval endpoints.

Common Pitfalls

Mixing Closed and Half-Open Semantics

Decide early whether intervals mean:

[start, end]

or:

[start, end)

Most geometry and sweep-line code is easier with half-open intervals.

Incorrect Tie-Breaking

For half-open intervals, process end events before start events at the same coordinate.

For closed intervals, the opposite may be required.

Merging When You Should Not

Touching intervals may or may not count as connected coverage. Define this explicitly.

Recomputing Merged Intervals Repeatedly

If many point queries are needed, merge once and query with binary search.

Ignoring Degenerate Intervals

Intervals with:

start = end

have zero length under half-open semantics. Decide whether to keep or discard them.

Complexity Analysis

Merging intervals:

O(n log n)

because of sorting.

Computing covered length after merging:

O(n)

Point query after preprocessing:

O(log n)

Two-set intersection:

O(n + m)

Dynamic coverage depends on the chosen data structure. A simple list is easy but slow. A segment tree supports efficient updates and coverage queries after coordinate compression.

Discussion

Interval geometry is the one-dimensional substrate behind many higher-dimensional algorithms. Sweep-line methods depend on it. Rectangle union area depends on it. Collision detection often reduces to interval overlap on projected axes. Scheduling systems, resource allocators, and temporal databases use the same patterns under different names.

The central discipline is semantic clarity. Once you decide whether intervals are closed, open, or half-open, every comparison, merge condition, and event-ordering rule follows from that choice.