Count intervals covering a point

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.