Interval Maps: Range Assignment over Disjoint Segments

Interval maps are an extension topic beyond most interviews; they pay off in hard design questions such as a range module, calendar booking, painting segments, or counting integers covered by added intervals, where a sorted structure of disjoint segments beats both brute force and heavyweight segment trees.

Intuition

Picture the integer line as a sequence of maximal segments with a constant value: positions 0 to 4 are "free", 5 to 11 are "booked", 12 onward are "free". Store only the segment starts in sorted order, each with its value; a segment ends where the next one starts. Every position belongs to exactly one segment, found by a binary search for the last start at or before it.

Two primitive operations do everything:

• split(x): make sure some segment starts exactly at x. If x lies inside a segment, cut it in two; both halves keep the old value.
• assign(l, r, v): set every position in [l, r) to v. Split at l and at r, delete every segment start strictly between them, and give the segment starting at l the value v. Optionally merge with neighbors that have the same value, so adjacent segments always differ.

Why it is fast: each assignment creates at most two new boundaries and deletes every boundary it covers. A boundary can only be deleted after it was created, so over q operations the total number of deletions is at most about 2q, an amortized O(1) per operation on top of the binary searches. Queries that walk the segments inside [l, r) cost the number of segments there; that is cheap when the walk is followed by an assignment of the same range (the segments disappear) or when the structure stays small.

With a balanced ordered map (C++ std::map, Java TreeMap) every split and delete is O(log n). Python has no built-in ordered map, so the template below keeps two parallel sorted lists and uses bisect: searches are O(log n) and insertions or deletions shift elements in O(n) memory moves, which is fast in practice for interview-sized inputs (the third-party sortedcontainers package is the usual drop-in upgrade).

When to use it in interviews / OAs

• A sequence of "set range to value" or "add / remove range" operations mixed with "is this whole range covered?" or "what is at position x?".
• Calendar and booking systems: reject a booking that overlaps an existing one, or count overlaps.
• Painting problems: "how much new area does each stroke paint?", "how many integers are covered after each insertion?".
• Merging a stream of numbers or intervals into disjoint intervals on the fly.
• Contest-style problems with random range assignments, where the number of segments stays small (beyond typical interviews).

Template

The interval map

from bisect import bisect_right


class IntervalMap:
    """A piecewise-constant function on the integers.
    Segment i covers positions starts[i] .. starts[i + 1] - 1 and holds vals[i]."""

    def __init__(self, default=0):
        self.starts = [-(1 << 62)]  # one segment covering everything
        self.vals = [default]

    def _split(self, x: int) -> int:
        """Make a segment start at x and return its index."""
        i = bisect_right(self.starts, x) - 1  # the segment containing x
        if self.starts[i] != x:
            i += 1
            self.starts.insert(i, x)
            self.vals.insert(i, self.vals[i - 1])  # the new piece keeps the old value
        return i

    def assign(self, l: int, r: int, v) -> None:
        """Set every position in [l, r) to v."""
        if l >= r:
            return
        i = self._split(l)
        j = self._split(r)  # r > l, so this split never moves index i
        del self.starts[i + 1:j]  # drop every boundary strictly inside [l, r)
        del self.vals[i + 1:j]
        self.vals[i] = v
        if i + 1 < len(self.vals) and self.vals[i + 1] == v:  # merge equal neighbours
            del self.starts[i + 1], self.vals[i + 1]
        if i > 0 and self.vals[i - 1] == v:
            del self.starts[i], self.vals[i]

    def get(self, x: int):
        return self.vals[bisect_right(self.starts, x) - 1]

    def segments(self, l: int, r: int):
        """Yield (start, end, value) pieces that exactly cover [l, r)."""
        if l >= r:
            return
        i = bisect_right(self.starts, l) - 1
        while i < len(self.starts) and self.starts[i] < r:
            end = self.starts[i + 1] if i + 1 < len(self.starts) else r
            yield max(self.starts[i], l), min(end, r), self.vals[i]
            i += 1

A range module with a covered-count

Track ranges of covered integers, answer whether a whole range is covered, and keep the total number of covered integers up to date. The count changes only inside the assigned range, so measure the covered part there just before overwriting it:

class RangeModule:
    def __init__(self):
        self.map = IntervalMap(False)
        self.covered = 0  # number of covered integers

    def _assign(self, l: int, r: int, value: bool) -> None:
        before = sum(e - s for s, e, v in self.map.segments(l, r) if v)
        self.map.assign(l, r, value)
        self.covered += (r - l if value else 0) - before

    def add_range(self, l: int, r: int) -> None:     # cover [l, r)
        self._assign(l, r, True)

    def remove_range(self, l: int, r: int) -> None:  # uncover [l, r)
        self._assign(l, r, False)

    def query_range(self, l: int, r: int) -> bool:   # is all of [l, r) covered?
        return all(v for _, _, v in self.map.segments(l, r))

    def count(self) -> int:
        return self.covered

Every segment the measurement walks over is deleted by the assignment that follows, so the walk is paid for by the same amortized argument.

Complexity

• With a balanced ordered map: O(log n) per split, amortized O(log n) per assignment, O(log n + k) for a query that reports k segments.
• With the Python lists above: the same number of searches and boundary changes, but each list insertion or deletion is an O(n) memory shift, usually acceptable up to about 10^5 operations.
• Space: O(number of segments), at most O(number of operations).

Common pitfalls

• Closed versus half-open ranges. Convert [l, r] to [l, r + 1) once at the boundary of your class and use half-open ranges everywhere inside.
• Split order with iterators. In C++ with std::set or std::map, split at r first and then at l, because splitting at l after r cannot invalidate the iterator for r, while the opposite order can. Index-based code like the template must make sure later splits do not shift earlier indices.
• Forgetting the sentinel segment(s), which makes lookups before the first start fail.
• Walking segments without assigning. A query that visits k segments costs O(k); many such queries over a fragmented map can degrade to O(n) each. Merge equal neighbors and keep the map canonical.
• Assuming contest folklore applies. The "it is fast because the data is random" analysis does not hold for adversarial interview inputs; rely only on the amortized assign argument.

Interview variations

• Range module: the class above.
• My calendar I: reject a booking if any segment in [start, end) is already booked, otherwise assign it.
• My calendar II and III: count overlaps instead; an ordered map of +1 at starts and -1 at ends (a difference array over an ordered map) gives the maximum overlap by a prefix-sum sweep.
• Count integers in intervals: the covered counter above.
• Data stream as disjoint intervals: add single points as [x, x + 1) and report the segments whose value is covered.
• Amount of new area painted each day: before assigning, measure how much of the range was unpainted.