给出很多间隔 [ai, bi]，找到与最多间隔数相交的间隔

给定很多间隔 [ai, bi]， 找到与间隔数量最多的间隔。 我们能在 O(nlogn) 或更好的时间内做到这一点吗？我只能想到 n^2 方法。

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

• if ai = aj，然后把ai第一个当量bi < bj
• if bi = bj，然后把bi第一个当量ai < aj
• if ai = bj，然后把ai first

将每个点标记为a or a b（也许保留一个长度的二进制数组2n去做这个）。遍历数组，跟踪有多少个间隔接触给定点（总计as 减去运行总计bs）。遇到的最大数量发生在重叠最多的间隔处。

This is O(n log n)由于间隔的排序。