有多少间隔包含另一个间隔？

Question

给定N个区间，有起点和终点。存在多少对这样的区间，这样一个区间包含另一个区间？

例如，如果给定的间隔是：
{2,3},{1,5},{0,10},{2,4}
那么我们有 5 对：
{0,10} 包含 {2,3}
{0,10} 包含 {2,4}
{0,10} 包含 {1,5}
{1,5} 包含 {2,4}
{1,5} 包含 {2,3}

我们只对此类对的数量感兴趣。你能帮我找到至少一个 O(N log N) 解决方案吗（O(N^2) 是微不足道的）？

注意：区间以{startpoint,endpoint}的形式给出，其中起点和终点最大为10^18。

提前致谢！

Answer 1

按 startpoint 排序，使用归并排序派生的 O(n log n) 时间算法计算 endpoint 列表中的反转次数。