Python程序：查找插入区间列表中一个可能的最小区间

假设我们有一个名为intervals的二维数字列表，其中每一行表示[开始，结束]（包含）区间。对于区间[a，b]（a < b），其大小为（b - a）。我们必须向给定的列表中添加一个区间，以便在合并所有区间后，我们恰好剩下一个范围。我们必须找到添加区间的最小可能大小。

因此，如果输入类似于intervals = [[15, 20],[30, 50]]，则输出将为10，因为我们可以添加区间[20, 30]，这是最小可能的区间。

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

  • events := 新列表
  • 对于intervals中的每个开始和结束时间s、e，执行以下操作：
    • 在events的末尾插入(s, 1)
    • 在events的末尾插入(e, -1)
  • 对列表events进行排序
  • curr_status := 0，last := null
  • interval := 一对[0, 0]
  • 对于events中的每个对(time, status)，执行以下操作：
    • 如果curr_status与0相同，并且last存在，并且time > last，则
      • 如果interval[0]与0相同，则
        • interval[0] := last
      • interval[1] := time
    • last := time
    • curr_status := curr_status + status
  • 返回interval[1] - interval[0]

让我们看看以下实现以获得更好的理解：

示例

 在线演示

class Solution:
   def solve(self, intervals):
      events = []
      for s, e in intervals:
         events.append((s, 1))
         events.append((e, -1))
      events.sort()
      curr_status = 0
      last = None
      interval = [0, 0]
      for time, status in events:
         if curr_status == 0 and last and time > last:
            if interval[0] == 0:
               interval[0] = last
            interval[1] = time
         last = time
         curr_status += status
      return interval[1] - interval[0]
ob = Solution()
intervals = [[15, 20],[30, 50]] print(ob.solve(intervals))

输入

[[15, 20],[30, 50]]

输出

10

更新于: 2020年10月19日

105 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告