Module 10 · Intervals and Sweep-Line Events

100. Active Interval Count Queries

Interview · Download this solution · All solutions and shared helpers

Problem

Given half-open intervals [start,end) with start<=end and query times, return the active interval count at each time in original query order. Empty intervals contribute zero. Queries may be unsorted and repeated.

Examples

Example 1

active_counts([(1,3),(2,5)], [0,1,2,3,5])
=> [0, 1, 2, 1, 0]

The count falls at each excluded right endpoint.

Example 2

active_counts([(2,2)], [2])
=> [0]

An empty interval contributes equal start and end counts.

Example 3

active_counts([], [1,9])
=> [0, 0]

No intervals are active at any query.

Reveal the worked solution and reasoning

Why this mechanism works

At time t, active intervals equal those that have started by t minus those that have ended by t. Sorting starts and ends separately makes each quantity an upper-bound query. Both use <=t because starts are included and ends are excluded.

State and boundaries

starts and ends are sorted endpoint multisets. bisect_right counts endpoints <= the query.

Protocol

Sort all starts and all ends.
For each t count starts<=t.
Subtract ends<=t.
Return counts in query order.

Visualization

interval [1,3)
t=1: started 1 - ended 0 = 1
t=3: started 1 - ended 1 = 0

Python implementation

from bisect import bisect_right

def active_counts(intervals, queries):
    starts = sorted(start for start, end in intervals)
    ends = sorted(end for start, end in intervals)
    return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

active_counts([(1,3),(2,5)], [0,1,2,3,5])

L4 <genexpr>: starts = sorted(start for start, end in intervals)
.0=list_iterator; start=1; end=3

L4 <genexpr>: starts = sorted(start for start, end in intervals)
.0=list_iterator; start=2; end=5

L4 <genexpr>: starts = sorted(start for start, end in intervals)
.0=list_iterator; start=2; end=5

L4 active_counts: starts = sorted(start for start, end in intervals)
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]

L5 <genexpr>: ends = sorted(end for start, end in intervals)
.0=list_iterator; start=1; end=3

L5 <genexpr>: ends = sorted(end for start, end in intervals)
.0=list_iterator; start=2; end=5

L5 <genexpr>: ends = sorted(end for start, end in intervals)
.0=list_iterator; start=2; end=5

L5 active_counts: ends = sorted(end for start, end in intervals)
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]; ends=[3, 5]

... 2 intermediate state changes omitted ...

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]; ends=[3, 5]; t=2

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]; ends=[3, 5]; t=3

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]; ends=[3, 5]; t=5

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(1, 3), (2, 5)]; queries=[0, 1, 2, 3, 5]; starts=[1, 2]; ends=[3, 5]

Result: [0, 1, 2, 1, 0]. The count falls at each excluded right endpoint.

active_counts([(2,2)], [2])

L4 <genexpr>: starts = sorted(start for start, end in intervals)
.0=list_iterator; start=2; end=2

L4 <genexpr>: starts = sorted(start for start, end in intervals)
.0=list_iterator; start=2; end=2

L4 active_counts: starts = sorted(start for start, end in intervals)
intervals=[(2, 2)]; queries=[2]; starts=[2]

L5 <genexpr>: ends = sorted(end for start, end in intervals)
.0=list_iterator; start=2; end=2

L5 <genexpr>: ends = sorted(end for start, end in intervals)
.0=list_iterator; start=2; end=2

L5 active_counts: ends = sorted(end for start, end in intervals)
intervals=[(2, 2)]; queries=[2]; starts=[2]; ends=[2]

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(2, 2)]; queries=[2]; starts=[2]; ends=[2]; t=2

L6 active_counts: return [bisect_right(starts, t) - bisect_right(ends, t) for t in queries]
intervals=[(2, 2)]; queries=[2]; starts=[2]; ends=[2]

Result: [0]. An empty interval contributes equal start and end counts.

Why the solution is correct

Every interval started by t contributes one to the first count. If it has also ended by t, it contributes one to the second and cancels. The uncanceled intervals satisfy start<=t<end, exactly the half-open membership condition.

Time and space

O(n log n+q log(n+1)) time and O(n+q) storage including answers.

Common mistakes

Using a lower bound for ends counts an interval at its excluded endpoint. Pairing endpoints after sorting is unnecessary because only aggregate counts are queried.

Reasoning card

State: starts and ends are sorted endpoint multisets. bisect_right counts endpoints <= the query.

Invariant: Counts include starts not after query and exclude ends at/before query for half-open rules.

Decision to rehearse: Sort starts, ends, and queries or use prefix events.

Finish: Return counts in query order

Transfer exercise

Return weighted active demand by storing prefix sums over sorted weighted endpoint events.