Intervals

What it is

An interval represents a continuous range between two endpoints. Interval algorithms organize these ranges to answer questions about overlap, coverage, scheduling, and containment.

Endpoint conventions matter:

• Closed [a, b]: both endpoints belong to the interval.
• Half-open [a, b): includes a, excludes b; usually require a < b.

Thus, [1, 3] and [3, 5] overlap, while [1, 3) and [3, 5) do not. Half-open intervals are especially useful for time spans because one activity can end exactly when another begins.

The naive approach often compares every interval with every other interval, costing quadratic time. Sorting exposes structure: earlier starts come first, overlap can often be resolved locally, and sweeping endpoints reduces continuous coverage to finitely many events. Heaps efficiently track intervals that remain relevant during a sweep.

How to recognize it

Look for these signals:

• Inputs contain start/end times, coordinate ranges, reservations, or allowable bounds.
• The task asks for a union, common intersection, uncovered fragments, or conflicting intervals.
• You need maximum simultaneous activity, total covered length, or regions covered by exactly one interval.
• Intervals must be assigned to reusable resources.
• You must remove intervals to satisfy an overlap limit.
• Many point queries ask which intervals contain each point.

Before choosing a technique, identify the endpoint convention, whether inputs are already sorted or disjoint, and whether the answer needs lengths, counts, or original interval identities.

The core technique

1. Sort by start and maintain a frontier

Use for merging overlapping intervals. Sort by start, then maintain the final merged interval. If the next start lies within its coverage, extend the end; otherwise, begin a new component.

def merge_closed(intervals):
    merged = []
    for start, end in sorted(intervals):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

The invariant is that the output represents the union of everything processed. Only its last interval can overlap the next input interval.

For half-open intervals, start < previous_end means actual overlap. Touching intervals may still be merged when representing their union, but they are not conflicting activities. Choose the comparison according to the operation.

Use for testing disjointness. After sorting, compare each end with the next start. Half-open intervals are disjoint when end <= next_start. If every right endpoint receives the same extension d, test end + d <= next_start. Consecutive checks suffice: ordered nonoverlapping neighbors imply global disjointness.

2. Combine boundaries directly

Use for a common allowable range. The intersection of several closed intervals is [L, R], where L is the greatest lower endpoint and R is the least upper endpoint. It exists exactly when L <= R. For half-open intervals, a nonempty intersection requires L < R.

When intersecting two sorted, internally disjoint interval lists, use two pointers. Compute the current intersection, then advance whichever interval ends first. That interval cannot contribute to any later intersection with the other current interval.

Use for subtraction. Removing [cut_start, cut_end) from an interval leaves zero, one, or two nonempty fragments:

def subtract(intervals, cut_start, cut_end):
    result = []
    for start, end in intervals:
        if cut_end <= start or end <= cut_start:
            result.append((start, end))
            continue
        if start < cut_start:
            result.append((start, cut_start))
        if cut_end < end:
            result.append((cut_end, end))
    return result

This assumes valid, ordered, disjoint half-open inputs and a nonempty cut. Process each original interval independently. Do not merge fragments across original boundaries when those boundaries must be preserved.

3. Sweep grouped endpoints

Use for coverage length and concurrency. Create a start and end event for every interval, then sort events by coordinate.

Maintain the active state between consecutive distinct coordinates. At coordinate x:

1. Attribute the span from the previous coordinate to x using the existing active state.
2. Apply every event at x as a group.
3. Continue with the updated state.

If the active count is positive, add the span length to union coverage. If it exceeds a limit, that span violates the concurrency constraint. To attribute uniquely covered spans, retain active interval IDs: when exactly one ID is active, credit that interval with the span length.

Grouping avoids artificial positive-length overlaps caused by endpoint ties. Endpoint-only questions still require explicit closed or half-open semantics. For closed intervals, starts at a coordinate overlap intervals ending there, even though that single point contributes no continuous length.

4. Sweep starts or queries with heaps

Use for resource allocation. Sort half-open intervals by start. An occupied heap stores (end, resource_id); a reusable-ID heap stores available IDs. Release resources whose end is at most the next start, then reuse the smallest ID or allocate a new one.

import heapq

def assign_resources(intervals):
    occupied, reusable = [], []
    next_id = 0
    answer = [None] * len(intervals)
    ordered = sorted(enumerate(intervals),
                     key=lambda item: (item[1][0], item[0]))
    for index, (start, end) in ordered:
        while occupied and occupied[0][0] <= start:
            _, resource = heapq.heappop(occupied)
            heapq.heappush(reusable, resource)
        if reusable:
            resource = heapq.heappop(reusable)
        else:
            resource = next_id
            next_id += 1
        answer[index] = resource
        heapq.heappush(occupied, (end, resource))
    return answer

Reusing any free resource minimizes resource count. Reusing the smallest ID adds deterministic numbering; simultaneous starts also need a defined tie order.

Use for deletion under a concurrency cap. Sweep starts while tracking active, retained intervals. If more than k overlap, discard the one ending latest. Keeping earlier-ending intervals frees capacity sooner. For k = 1, this is closely related to selecting nonoverlapping intervals by earliest finish. General implementations need efficient expiration and latest-end selection, often using heaps and lazy invalidation.

Use for shortest-covering-interval queries. Sort intervals by start and queries by coordinate. Insert intervals whose starts are at most the query into a min-heap keyed by length. Repeatedly remove the top while it no longer contains the query. The remaining top is the shortest covering interval. Expired entries buried below it can stay until they reach the top; preserve original query indices to restore answer order.

Common mistakes

• Mixing closed and half-open overlap tests.
• Replacing a merged end instead of taking its maximum.
• Assuming sorted intervals are also disjoint.
• Counting endpoint events individually when span attribution requires grouping.
• Treating elapsed time as an inclusive integer-point count.
• Using an end-ordered heap when queries require length ordering.
• Forgetting stale-entry checks after heap-based deletions.
• Applying earliest-finish deletion greediness to weighted intervals; weights require a different argument.

Complexity

• Sorting and merging: O(n log n) time; scanning is O(n). Output uses up to O(n) space.
• Common intersection: O(n) time and O(1) auxiliary space. Two-list intersection costs O(n + m).
• Subtraction: O(n) time, with up to two output fragments per input interval.
• Endpoint sweeps and heap scheduling: typically O(n log n) time and O(n) space. Each event or heap entry is processed a bounded number of times.
• Containment queries: O(n log n + q log q + (n + q) log n) time and O(n + q) space, including sorting and restored output order.

Already sorted inputs can eliminate sorting costs, but heap operations may still dominate.