Find integer in most intervals
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### 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?
Quick Answer: This question evaluates a candidate's ability to reason about interval overlap counting, manage range endpoints efficiently, and balance time-space trade-offs when identifying points that maximize coverage.
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
Hints
- Transform intervals into events: +1 at ai and -1 at bi+1 (difference array idea for inclusive intervals).
- Sort event positions and compute a running sum (prefix) to track active intervals; the first position reaching a new maximum is your answer.
- 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.