在Python中查找列表区间的最长间隔长度

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

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

要解决这个问题，我们将遵循以下步骤 –

• 排序列表间隔
• union：=间隔列表中的第一个间隔
• 最佳值：= union[end] – union[start] +1
• 对于intervals中除第一个以外的每个开始时间s和结束时间e，执行以下操作
  • 如果s <= union [end]，则
    • union [end]：= union [end]和e的最大值
  • 否则，
    • union：=新区间[s，e]
  • best：= best和union[end] – union[start] +1的最大值
• 返回best

让我们看一下以下实现，以获得更好的理解-

更多Python相关文章，请阅读：Python 教程

示例

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