Python程序：合并目标区间查找区间

假设我们有一列不重叠的区间。这些区间按结束时间排序。我们还有一个目标区间，找到合并目标区间后的最终区间，以便区间仍然不重叠且排序。

因此，如果输入类似于 intervals = [[1, 15],[25, 35],[75, 90]]，target = [10, 30]，则输出将为 [[1, 35], [75, 90]]，因为前两个区间 [1, 15] 和 [25, 35] 已合并。

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

  • 将目标区间插入到iv的末尾

  • 根据起始时间对iv进行排序

  • res := 一个包含第一个区间的新列表

  • i := 1

  • 当 i < iv 的大小 时，执行以下操作：

    • 如果 iv[i] 的起始时间 <= res 的最后一个区间的结束时间，则

      • res 的最后一个区间的结束时间 = (res 的最后一个区间的结束时间和 iv[i] 的结束时间)中的最大值

    • 否则：

      • 将 iv[i] 插入到 res 的末尾

    • i := i + 1

  • 返回 res

示例 (Python)

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

 在线演示

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

输入

[[1, 15],[25, 35],[75, 90]], [10, 30]

输出

[[1, 35], [75, 90]]

更新于：2020年12月22日

112 次浏览

开启您的职业生涯

通过完成课程获得认证

开始
广告