Find Most Frequently Repeating Integer in Series of Ranges

Question

I've got this exercise where I can't figure out what I'm missing. It's actually very similar to an existing question, but not the same and the solution is probably not the same. The existing question: Finding the most frequent number from a set of ranges -

The problem:

---

You are given n ranges [a_i, b_i] in the range of [0, n^d], where d is a constant positive integer. a_i, b_i are also integers, and 0 <= a_i <= b_i <= n^d for each i (i = 1, ..., n).

Write an algorithm to find the integer z that appears in the greatest amount of ranges [a_i, b_i]. The complexity must be linear (as a function of n, d).

---

It seems to me like a classic counting/radix sort problem: use k = n as the radix and the complexity of the sort becomes O(d*n). The question is, what to do next? I'm a bit stuck on this. In the related question, there is an assumption that the range can only be a certain size, while in my question there is no such assumption, and theoretically there can be a range of [0, n^d] and anything in between.

Random example:

Input: [1, 3], [5, 10], [5, 11], [6, 17], [8, 9], [9, 21], [11, 15], [12, 12]
Output: 9

Answer 1

Sorting is a good idea (radix sort seems to be the way to go), but I wouldn't sort the intervals. Instead, I would use the sweep line style approach. Imagine the intervals being drawn on a number line from 0 to n^d. Now we "sweep" from left to right.

The interesting points were the situation of how many intervals intersect our current position can change, are the start/end points of our intervals. Note that we can always choose one of the start or end points as the solution as well.

So we just consider those points and sweep from left to right:

events = start points UNION end points
sort events (rank start points before end points in case of a tie)
count = 0
max = 0
for each event x in sorted order
    if x is start point
        count++
    if x is end point
        count--
    if count > max
        max = count
        result = x