Python - 确定3个范围的重叠部分

Question

我有一个关于使用Python确定三个范围的重叠而不使用任何现有库的问题：

例如，如果我有三个范围（10,20）（15,25）（18,30），我应该如何找到它们之间的重叠部分？

我的答案应该是（18,19,20）。

任何帮助都将不胜感激。谢谢！

- user1418321

---

还有，你的那些给定范围是什么意思？在 Python 中，范围对象 (range(10, 20)) 的取值范围是第二个值之前的数，不包括第二个值，所以预期输出为 (18, 19)。 - Gareth Latty

Duplicate - Steve

@Steve 不是重复的问题，那个问题要求特定的两个范围，而这个问题要求三个。虽然可以推断出来，但它不是重复的。显然，一个通用的答案（如此处所给出的）是更好的选择。 - Gareth Latty

Answer 1

重叠部分从最高的起点到最低的终点： ```

重叠部分从最高的起点到最低的终点：

```

ranges = [(10,20), (15,25), (18,30)]
starts, ends = zip(*ranges)
result = range(max(starts), min(ends) + 1)

测试：

>>> print(*result)
18 19 20

- Reinstate Monica

---

非常感谢。然而，我有许多这样的范围（大约有一百万个）。即有3个范围，但是有大约一百万个这样的比较需要进行。 您能告诉我一种计算速度快的方法来比较这一百万个范围吗？ - user1418321

在我的电脑上大约需要2秒钟。除非您实际上是将范围创建为列表（例如使用Python 2.x并且不使用xrange），并且结果非常大，否则这将很快。如果您必须创建实际的列表并且它们非常大，则没有任何方法可以帮助。 - Reinstate Monica

Answer 2

虽然WolframH的答案是这种情况下最好的答案，但如果您不需要担心重复元素，则可以使用集合及其intersection操作来获得更一般的查找重叠解决方案。

>>> set(range(10, 21)) & set(range(15, 26)) & set(range(18, 31))
{18, 19, 20}

或者，更为通用的解决方案是：

ranges = [(10, 20), (15, 25), (18, 30)]
set.intersection(*(set(range(start, finish+1)) for start, finish in ranges))

- Gareth Latty

---

很好，你甚至不需要使用 reduce：set.intersection(*(set(range(start, finish+1)) for start, finish in ranges))。 - Reinstate Monica

@WolframH 很好，我不知道set.intersection()可以接受多个集合，太棒了。每当我不得不使用reduce()时，我总是感到很不舒服。已编辑。 - Gareth Latty