Count intervals covering a point

Question: Count intervals covering a point

Companies: Google, Netflix

Difficulty: Medium

Problem statement

Build a data structure over a fixed list of closed intervals on the integer number line that answers many point queries quickly.

An interval [l, r] covers a point x when l <= x <= r. Both endpoints count.

Implement IntervalCounter:

• IntervalCounter(intervals: list[tuple[int, int]]): store the intervals. Each has l <= r. Intervals can repeat, and coordinates can be negative or very large.
• count(x: int) -> int: return how many stored intervals cover x.

count is called many times, so it should be faster than scanning every interval.

Constraints

• 0 <= len(intervals) <= 10^5
• -10^9 <= l <= r <= 10^9
• Up to 10^5 calls to count

Example 1

c = IntervalCounter([(3, 7), (5, 9), (12, 12)])
c.count(2)   # 0
c.count(5)   # 2  -> [3,7] and [5,9]
c.count(9)   # 1  -> [5,9]; the right endpoint is included
c.count(12)  # 1  -> [12,12]

Example 2

c = IntervalCounter([(-4, 0), (-4, 0), (-1, 6)])
c.count(-4)  # 2
c.count(0)   # 3
c.count(7)   # 0

Be ready to extend it: intervals added and removed after construction, and the point covered by the most intervals.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Restate the question. An interval [l, r] covers x exactly when it
has started (l <= x) and has not yet ended (r >= x). So the answer is

count(x) = #(intervals with l <= x) - #(intervals with r < x)

Every interval with r < x also has l <= r < x, so it is inside the first
group. Subtracting removes exactly the intervals that started and already
ended. What is left is the set that started and is still open, which is the
set covering x.

Brute force. Scan all n intervals for each query: O(n) per query. It
is correct and a fine first answer, but the question says the structure is
asked "any number of times", so the interviewer wants query time below
linear.

Point prefix table. If coordinates are small integers, build a difference
array (+1 at l, -1 at r + 1) and take a prefix sum. Queries become
O(1), but memory is O(max coordinate). That fails on coordinates like
10^9 or negative values unless you compress them.

Optimal: two sorted arrays. Keep the start points sorted and the end
points sorted, each on its own. The intervals do not need to stay paired,
because the formula above counts starts and ends independently.

• #(l <= x) is bisect_right(starts, x).
• #(r < x) is bisect_left(ends, x).

Build is O(n log n), each query is O(log n), and memory is O(n). This
is the same "starts minus ends" idea as Meeting Rooms II, applied at one
point instead of swept over all points.

Invariants.

• starts and ends are sorted and have the same length n.
• Inclusive ends: bisect_right on starts (an interval starting at x
  counts) and bisect_left on ends (an interval ending at x still counts).
  Swapping either one is the classic off-by-one bug.
• The result is always between 0 and n.

Dynamic version (common part 2). When intervals arrive after
construction, sorted Python lists cost O(n) per insert. If all coordinates
are known in advance (offline), compress them and keep two Fenwick trees,
one counting starts and one counting ends. Each add, remove, and query is
then O(log m). The code below includes that version.

Code

from bisect import bisect_left, bisect_right
from typing import Iterable


class IntervalCounter:
    """Static: counts closed intervals [l, r] that contain a point."""

    def __init__(self, intervals: Iterable[tuple[int, int]]) -> None:
        starts: list[int] = []
        ends: list[int] = []
        for l, r in intervals:
            if l > r:
                raise ValueError(f"bad interval [{l}, {r}]")
            starts.append(l)
            ends.append(r)
        self._starts = sorted(starts)
        self._ends = sorted(ends)

    def count(self, x: int) -> int:
        started = bisect_right(self._starts, x)   # l <= x
        finished = bisect_left(self._ends, x)     # r <  x
        return started - finished


class _Fenwick:
    def __init__(self, size: int) -> None:
        self._tree = [0] * (size + 1)

    def add(self, i: int, delta: int) -> None:   # i is 0-based
        i += 1
        while i < len(self._tree):
            self._tree[i] += delta
            i += i & -i

    def prefix(self, i: int) -> int:             # sum of positions [0, i)
        total = 0
        while i > 0:
            total += self._tree[i]
            i -= i & -i
        return total


class DynamicIntervalCounter:
    """Follow-up: add/remove intervals online. Endpoints must come from a
    coordinate universe known up front (offline compression)."""

    def __init__(self, coordinates: Iterable[int]) -> None:
        self._coords = sorted(set(coordinates))
        self._starts = _Fenwick(len(self._coords))
        self._ends = _Fenwick(len(self._coords))
        self._size = 0

    def _index(self, v: int) -> int:
        i = bisect_left(self._coords, v)
        if i == len(self._coords) or self._coords[i] != v:
            raise KeyError(f"coordinate {v} was not declared")
        return i

    def add(self, l: int, r: int, delta: int = 1) -> None:
        if l > r:
            raise ValueError(f"bad interval [{l}, {r}]")
        self._starts.add(self._index(l), delta)
        self._ends.add(self._index(r), delta)
        self._size += delta

    def remove(self, l: int, r: int) -> None:
        self.add(l, r, -1)   # caller guarantees the interval is present

    def count(self, x: int) -> int:
        # x itself need not be a declared coordinate.
        started = self._starts.prefix(bisect_right(self._coords, x))
        finished = self._ends.prefix(bisect_left(self._coords, x))
        return started - finished


if __name__ == "__main__":
    c = IntervalCounter([(1, 4), (2, 6), (5, 8), (10, 10)])
    assert [c.count(x) for x in (0, 1, 2, 4, 5, 6, 7, 9, 10, 11)] == [
        0, 1, 2, 2, 2, 2, 1, 0, 1, 0]
    assert IntervalCounter([]).count(3) == 0
    neg = IntervalCounter([(-5, -1), (-3, 3), (-3, 3)])
    assert neg.count(-3) == 3 and neg.count(0) == 2 and neg.count(4) == 0

    d = DynamicIntervalCounter([1, 4, 2, 6, 5, 8])
    d.add(1, 4)
    d.add(2, 6)
    assert d.count(3) == 2 and d.count(7) == 0
    d.add(5, 8)
    assert d.count(5) == 2 and d.count(7) == 1
    d.remove(2, 6)
    assert d.count(5) == 1 and d.count(3) == 1
    print("all tests passed")

Complexity

Let n be the number of intervals and m the number of distinct declared
coordinates.

Test cases

• Intervals [(1,4), (2,6), (5,8), (10,10)]:
  • count(0) -> 0 (before everything)
  • count(1) -> 1 (left endpoint is inclusive)
  • count(4) -> 2 (right endpoint of [1,4] is inclusive)
  • count(5) -> 2, count(7) -> 1, count(9) -> 0 (gap)
  • count(10) -> 1 (single-point interval), count(11) -> 0
• No intervals: count(3) -> 0.
• Negative coordinates and duplicates [(-5,-1), (-3,3), (-3,3)]:
  count(-3) -> 3, count(0) -> 2, count(4) -> 0.
• Invalid interval (5, 2) raises ValueError.
• Dynamic: add [1,4], [2,6] -> count(3) = 2; add [5,8] ->
  count(5) = 2; remove [2,6] -> count(5) = 1, count(3) = 1.
• Large coordinates such as [(-10**9, 10**9)]: count(0) -> 1 with no
  memory blow-up.

Follow-ups

1. Intervals arrive online (add and remove). Sorted lists make insertion
   O(n). With a known coordinate set, use two Fenwick trees as in the code
   (O(log m) each). With unknown coordinates, use a balanced BST or
   SortedList with rank queries, or a dynamic (lazily allocated) segment
   tree over the full value range.
2. Maximum coverage / busiest point (Meeting Rooms II). Sweep the
   events: +1 at l, -1 just after r. Sort with starts before ends at
   equal coordinates (inclusive ends), track the running maximum and where it
   happens. O(n log n).
3. Many queries in one batch. Sort the queries and sweep starts and ends
   with two pointers in O((n + q) log(n + q)). Return answers in the
   original query order. This avoids the binary searches and is good when
   all queries are known up front.
4. Count intervals that overlap a query range [a, b]. An interval
   misses [a, b] only if r < a or l > b, and both cannot hold at once.
   So the answer is n - bisect_left(ends, a) - (n - bisect_right(starts, b)).
   It uses the same two sorted arrays.
5. Return the covering intervals, not just the count. Use an interval
   tree or a centered interval tree for O(log n + k) per query, where k
   is the output size. Half-open intervals [l, r) only change the bisect
   choice on ends (bisect_right(ends, x)).

Interviewer expectations

Mid-level (L4)

• Gives the O(n) scan, then reaches the sorted starts and ends idea with
  some hints.
• Gets the inclusive boundary right (bisect_right vs bisect_left) and
  tests endpoints.
• States build and query complexity correctly.

Senior (L5)

• Derives "started minus already ended" on their own and explains why
  pairing is not needed.
• Handles empty input, duplicates, negative and very large coordinates, and
  says why a dense difference array fails there.
• Handles the online follow-up with a Fenwick tree or an ordered structure,
  and links the problem to Meeting Rooms II for the busiest point.

Staff (L6+)

• Asks about the workload first (static vs dynamic, query to update ratio,
  online vs batch, need the intervals or just a count) and picks a structure
  for each case.
• Compares Fenwick with compression, dynamic segment trees, interval trees,
  and offline sweeps in terms of memory, latency, and how easy they are to
  operate.
• Talks about scale: sharding by coordinate range, merging counts across
  shards, and keeping a rebuilt static snapshot plus a small delta buffer for
  recent writes.