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
Solution
from typing import List, Dict
def most_overlapped_point(intervals: List[List[int]]) -> int:
# Return the smallest integer that lies in the maximum number of closed intervals.
events: Dict[int, int] = {}
for a, b in intervals:
events[a] = events.get(a, 0) + 1
events[b + 1] = events.get(b + 1, 0) - 1
max_count = -1
best_x = 0
curr = 0
for x in sorted(events.keys()):
curr += events[x]
if curr > max_count:
max_count = curr
best_x = x
return best_x
Explanation
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).
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.