Count Overlapping Intervals at a Query Time

Problem Given a list of time intervals and a stream of point-in-time queries, answer for each query how many intervals are active (overlapping) at that instant.

Input / Output

• Input: n intervals [(s1,e1), …, (sn,en)] and q query times t1..tq.
• Output: for each query, the count of intervals containing that time — or the intervals themselves in the reporting variant.

Constraints

• n and q up to ~10^5 each, so a per-query linear scan at O(n·q) is far too slow.
• Clarify whether endpoints are inclusive or half-open — it decides how start and end events at the same timestamp are ordered.
• The intervals are known upfront (offline); an online version where intervals arrive between queries needs a different structure.

Example

• Intervals [(1,5),(2,6),(8,10)], query t=3 → 2, since (1,5) and (2,6) are both active.
• Query t=7 → 0; the gap between 6 and 8 has no coverage.
• Query t=5 → 2 if ends are inclusive, but 1 if half-open — the tie case worth raising before coding.