程序找到一个最小可能的间隔以插入到Python的间隔列表中

Z时代
2024-01-10
分类：综合

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

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

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

事件：=一个新列表
对于每个开始时间和结束时间s（以e为间隔）

在事件结束时插入(s,1)
在事件结束时插入(e,-1)

排序列表事件
curr_status：= 0，最后一个：= null
间隔：=一对[0，0]
对于事件中的每个对（时间，状态），请执行

如果interval [0]与0相同，则
interval [1]：=时间
interval [0]：=最后
如果curr_status等于0，last和time> last，则
最后：=时间
curr_status：= curr_status +状态

返回间隔[1]-间隔[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))