在 Python 中查找相交区间

假设我们有一个区间列表，其中每个区间都像 [开始，结束] 这样表示区间的开始和结束时间（包含），我们需要找到它们的交集，即位于所有给定区间内的区间。

因此，如果输入类似于 [[10, 110],[20, 60],[25, 75]]，则输出将为 [25, 60]

为了解决这个问题，我们将遵循以下步骤：

  • start，end := 从区间列表中删除最后一个元素后的区间
  • 当 intervals 不为空时，执行以下操作
    • start_temp，end_temp := 从区间列表中删除最后一个元素后的区间
    • start := start 和 start_temp 的最大值
    • end := end 和 end_temp 的最小值
  • 返回一个区间 [start, end]

让我们看看下面的实现以更好地理解：

示例

 在线演示

class Solution:
   def solve(self, intervals):
      start, end = intervals.pop()
      while intervals:
         start_temp, end_temp = intervals.pop()
         start = max(start, start_temp)
         end = min(end, end_temp)
      return [start, end]
ob = Solution()
intervals = [[10, 110],[20, 60],[25, 75]]
print(ob.solve(intervals))

输入

[[10, 110],[20, 60],[25, 75]]

输出

[25, 60]

更新于：2020-09-23

3K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告