Most Frequent Number in Intervals

Description

You are given a list of list of integers intervals where each element contains the inclusive interval [start, end].

Return the most frequently occurring number in the intervals. If there are ties, return the smallest number.

Constraints:

• n ≤ 100,000 where n is the length of intervals

Example 1

Input

intervals = [
    [1, 4],
    [3, 5],
    [6, 9],
    [7, 9]
]

Output

3

Explanation

The most frequent numbers are [3, 4, 7, 8, 9] and they all occur twice but 3 is the smallest one.

---

Intuition

Implementation

int solve(vector<vector<int>> &intervals) {
    map<int, int> map;
    for (auto &interval : intervals) {
        map[interval[0]]++;
        map[interval[1] + 1]--;
    }
    int level = 0, max_level = 0, ans = 0;
    for (auto &pair : map) {
        level += pair.second;
        if (level > max_level) {
            max_level = level;
            ans = pair.first;
        }
    }
    return ans;
}

Time Complexity

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