Maximum overlap of closed intervals

Given a list of closed intervals [start, end] (both endpoints included), return the largest number of intervals that contain one point on the number line.

max_overlap(intervals: list[tuple[int, int]]) -> int

Two intervals that only share an endpoint overlap at that point. For example, [2, 6] and [6, 9] both contain 6.

Constraints

• 0 <= len(intervals) <= 10^5
• -10^9 <= start <= end <= 10^9
• Intervals can repeat, and an interval can be a single point (start == end).
• Return 0 for an empty list.

Example 1

intervals = [[2, 6], [6, 9], [10, 11]]
output: 2   # the point 6 is in [2, 6] and [6, 9]

Example 2

intervals = [[1, 20], [4, 7], [5, 12], [15, 18]]
output: 3   # points 5, 6 and 7 are in [1, 20], [4, 7] and [5, 12]

Part 2. After preprocessing the intervals once, answer many queries count(x): how many intervals contain the point x? Each query should be faster than O(n).