algorithm - 在范围系列中找到最频繁重复的整数

Question

我有这个练习，但我不知道我错过了什么。它实际上与现有问题非常相似，但不相同，解决方案可能也不相同。 现有问题:Finding the most frequent number from a set of ranges -

问题:

---

给你 n 个范围 [a_i, b_i]，范围是 [0, n^d]，其中 d 是一个恒定的正整数。 a_i, b_i 也是整数, 0 <= a_i <= b_i <= n ^d 对于每个 i (i = 1, ..., n)。

编写一个算法，找出在 [a_i, b_i] 范围内出现次数最多的整数 z。复杂度必须是线性的(作​​为 n、d 的函数)。

---

在我看来，这就像一个经典的计数/基数排序问题:使用 k = n 作为基数，排序的复杂度变为 O(d*n)。问题是，下一步怎么办？我有点坚持这一点。在相关问题中，假设范围只能是一定大小，而在我的问题中没有这样的假设，理论上可以有范围 [0, n^d]以及介于两者之间的任何东西。

随机示例:

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

Answer 1

排序是个好主意(基数排序似乎是可行的方法)，但我不会对间隔进行排序。相反，我会使用扫描线样式方法。想象一下在从 0 到 n^d 的数字线上绘制的间隔。现在我们从左到右“扫描”。

有趣的是，我们当前位置可以改变多少个区间相交的情况，是我们区间的起点/终点。请注意，我们也始终可以选择起点或终点之一作为解决方案。

所以我们只考虑那些点并从左到右扫过:

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