用 Python 编写程序查找重叠区间并按升序返回它们

假设我们有一个闭区间列表和另一个区间列表。每个列表单独来看都是不重叠的，并且按非降序排序。我们必须找到按非递减顺序排序的两个区间的重叠部分。

因此，如果输入为 inv1 = [[50, 100],[190, 270],[310, 330]] inv2 = [[40, 120],[180, 190]]，则输出为 [[50, 100], [190, 190]]

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

• ans := a new list
• i := 0, j := 0
• 当 i < A 的大小和 j < B 的大小时，执行
  • if start <= end, then
    • insert interval [start, end] into ans
  • if A[i, 1] < B[j, 1], then
    • i := i + 1
  • 否则，
    • j := j + 1
• 返回 ans

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

示例

class Solution:
   def solve(self, A, B):
      ans = []
      i = 0
      j = 0
      while i < len(A) and j < len(B):
         start = max(A[i][0], B[j][0])
         end = min(A[i][1], B[j][1])
         if start <= end:
            ans.append([start, end])
            if A[i][1] < B[j][1]:
               i += 1
            else:
               j += 1
         return ans
ob = Solution()
inv1 = [[50, 100],[190, 270],[310, 330]]
inv2 = [[40, 120],[180, 190]]
print(ob.solve(inv1, inv2))

输入

[[50, 100],[190, 270],[310, 330]], [[40, 120],[180, 190]]

输出

[[50, 100], [190, 190]]

相关文章

• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/