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

假设我们有一个二维数字列表,称为间隔,其中每行代表[开始,结束](包括)间隔。对于间隔[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))

    输入值

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

    输出结果

    10
    猜你喜欢