Find integer in most intervals

Question

Given N integer intervals [ai, bi] (positive integers), find an integer that belongs to the maximum number of intervals (return any such integer if several exist). Follow-up: When every endpoint is < M and M is small, how would you optimize?

Integer With Maximum Interval Overlaps

You are given N closed intervals of positive integers, intervals[i] = [ai, bi] with ai <= bi. Find an integer x that lies in the maximum number of intervals. If multiple integers achieve this maximum coverage, return the smallest such integer.

Constraints

• 1 <= N <= 200000
• 1 <= ai <= bi <= 10^9
• Intervals are closed: x is covered by [a,b] if a <= x <= b
• If multiple integers tie for maximum coverage, return the smallest integer

Examples

Example 1

Input: intervals = [[1,4],[2,5],[7,9]]
Output: 2

Explanation: Coverage counts: [1]=1, [2..4]=2, [5]=1, [7..9]=1. The maximum is 2 starting at 2, so return 2.

Example 2

Input: intervals = [[5,5],[1,3],[4,6],[2,8]]
Output: 5

Explanation: Counts peak at x=5 with 3 overlapping intervals: [5,5], [4,6], [2,8].

Hints

1. Transform intervals into events: +1 at ai and -1 at bi+1 (difference array idea for inclusive intervals).
2. Sort event positions and compute a running sum (prefix) to track active intervals; the first position reaching a new maximum is your answer.
3. If all endpoints are less than a small M, use an array of length M+2 for O(N+M) time via difference array and prefix sums.

Approach

Use a sweep-line over integer coordinates with a difference map: for each [a,b], add +1 at a and -1 at b+1. After sorting the event positions, a running prefix sum gives the number of active intervals at each integer. Track the maximum prefix value and record the smallest position where it occurs. This corresponds to the smallest integer covered by the most intervals. For the follow-up where all endpoints are less than a small M, build an array diff of size M+2, apply the same +1/-1 updates, compute a prefix sum, and find the index with the maximum value in O(N+M) time.

• Time complexity: O(N log N)
• Space complexity: O(N)