用 Python 编写程序，查找一个最小可能间隔以插入间隔列表

pythonserver side programmingprogramming更新于 2026/2/2 6:36:17

假设我们有一个 2D 数字列表，称为间隔，其中每行代表 [开始，结束](含)间隔。对于间隔 [a, b](a < b)，其大小为 (b - a)。我们必须将一个间隔添加到给定列表中，以便在合并所有间隔后，我们只剩下一个范围。我们必须找到添加间隔的最小可能大小。

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

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

events := a new list
对于间隔中的每个开始和结束时间 s、e，执行
- 在事件末尾插入 (s, 1)
- 在事件末尾插入 (e, -1)
对事件列表进行排序
curr_status := 0, last := null
interval := a pair [0, 0]
对于事件中的每个对 (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))