Python算法：如何高效地判断两个整数集合是否相交？

Question

给定一个范围 [2004, 2008]，最快的方法是什么来判断这个范围是否和其他范围有交集？

其实我在处理一个数据库的问题，表里有两列，一列是下限，另一列是上限。我的任务是找到所有和给定的这个范围（比如 [2004, 2008]）有交集的行。

我在使用mongodb，这个功能是数据库本身支持的吗？也就是说，有没有现成的关键词可以用来实现这个功能？因为我的用户量很大，所以我希望这个任务能尽快完成。

补充一下，数据库表里包含以下几行：

20 30
10 50
60 90
...

给定输入范围 (25 40)，我想返回那些表示范围的行，这些行和给定的范围有交集。

所以返回的结果是：(20 30),(10 50)

Answer 1

MongoDB不支持交集操作。你可以在Python中使用集合的intersection()方法来实现交集。

Answer 2

试试这个，假设 low 和 high 是你要设置的范围：

db.ranges.find({'low': {'$lt': self.high}, 'high': {'$gt': self.low}})

如果你希望你的查询包含边界值，可以把 $lte 和 $gte 替换掉。

Answer 3

我对MongoDB一点都不了解，但你基本上是在寻找

从表中选择所有数据，条件是下限不大于2008或者上限不小于2004。