python - Discarding isolated pairs of points

Question

I have a a list of a million pairs of integers (a,b). How can I prepare a data structure in python with the following property? When I see a new pair of integers I would like to be able to tell if it overlaps any existing pair in my list very quickly? Assuming b > a and d > c I say that (a,b) and (c,d) overlap if (a <= c and b >= c) or (a<=d and b>=d) or both a and b are between c and d.

Can this be done somehow in log time?

Answer 1

您可以预处理现有数据，使您的数据由不重叠的间隔组成。也就是说，如果 (a,b) 和 (c,d) 相交，您可以将它们合并为单个区间 (a,d) 或 (a,b) 或 (c,b) 或 (c,d)，具体取决于重叠的性质。

有关此步骤的更多详细信息：根据它们的起点（终点作为辅助键）对间隔进行排序。合并步骤可以在 O(n) 时间完成。

现在，对合并的区间进行排序。为了测试重叠，您可以进行两次二进制搜索。