小编tat*_*dha的帖子

给定两个列表，每个列表包含N个间隔（数字线的子集），每个间隔具有起点和终点的形式。一个列表中的这些间隔中有多少对包含另一列表中的间隔？

例如：

如果列表A是{(1,7), (2,9)}且列表B是{(3,6), (5,8)}

那么，其中A的间隔包含B中的间隔的对的计数为3对：

(1,7),(3,6)
(2,9)(3,6)
(2,9)(5,8)

目标是射击O（n log n）。

我目前的算法是先按x坐标排序，然后将其作为一个列表。然后按y坐标对列表进行排序，并计算两个列表之间的倒数。但是我的问题是为什么这行得通？任何见识将不胜感激。

我目前正在可视化的方式是以下几何方式（线的每个交点都是num求逆的计数）：

注意：我不确定如何在列表列表中检查反转。只是试图找到一种可以给出O（n log n）的方法。如果有其他方法很高兴听到建议。