给出大量间隔[ai,bi],找到与最多间隔相交的间隔

Question

给定大量间隔[ai,bi],找到与最多间隔相交的间隔.我们可以在O(nlogn)或更好的地方做到这一点吗？我只能想到^ 2方法.

Answer 1

假设间隔给出为(a1,b1), ..., (an,bn).制作一个长度排序的数组,2n其中关系被破坏

• if ai = aj,然后ai先放iffbi < bj
• if bi = bj,然后bi先放iffai < aj
• 如果ai = bj,那么ai先放

将每个点标记为a a或a b(可能保留长度的二进制数组2n来执行此操作).遍历数组,跟踪触摸给定点的间隔数(运行总数as减去运行总数bs).遇到的最大数量发生在重叠最多的时间间隔.

这是O(n log n)由于间隔的分类.