程序从Python中的间隔列表中查找最长间隔的长度

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

假设我们有一个间隔列表，其中每个间隔的格式为[start，end]。我们必须找到可以合并任意数量的重叠间隔的最长间隔。

因此，如果输入类似于[[1，6]，[4，9]，[5，6]，[11，14]，[16，20]]，则输出将为9，如合并后，我们有长度为9的间隔[1，9]。

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

  • 排序列表间隔

  • union：=间隔列表中的第一个间隔

  • 最佳：= union [end]-union [start] + 1

  • 对于除第一个时间间隔以外的每个开始时间s和结束时间e，执行

    • union：=一个新的间隔[s，e]

    • union [end]：= union [end]和e的最大值

    • 如果s <= union [end]，则

    • 除此以外，

    • best：= best和union [end]的最大值-union [start] + 1

    • 最好的回报

    让我们看下面的实现以更好地理解-

    示例

    class Solution:
       def solve(self, intervals):
          intervals.sort()
          union = intervals[0]
          best = union[1] - union[0] + 1
          for s, e in intervals[1:]:
             if s <= union[1]:
                union[1] = max(union[1], e)
             else:
                union = [s, e]
                best = max(best, union[1] - union[0] + 1)
          return best
    ob = Solution()intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
    print(ob.solve(intervals))

    输入项

    [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

    输出结果

    9

    以上是 程序从Python中的间隔列表中查找最长间隔的长度 的全部内容， 来源链接： utcz.com/z/316087.html

    回到顶部