Python 中合并区间并按升序排列的程序

假设我们有一个列表间隔，即我们要找到它们的并集，并按排序顺序排列。

所以，如果输入像 inv = [[2, 5],[4, 10],[20, 25]], 那么输出将为 [[2, 10], [20, 25]]

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

• 对间隔列表进行排序
• ans := 一个新列表
• 对于间隔列表中的每个开始时间和结束时间 (s, e)，执行以下操作
  • 如果 ans 不为空且 s <= ans 的最后一个间隔的结束时间，那么
    • ans 的最后一个间隔的结束时间 := e 和 ans 的最后一个间隔的结束时间的最大值
  • 其他情况下，
    • 将区间 [s, e] 插入到 ans 中
• 返回 ans

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

示例

 在线演示

class Solution:
   def solve(self, intervals):
      intervals.sort()
      ans = []
      for s, e in intervals:
         if ans and s <= ans[-1][1]:
            ans[-1][1] = max(ans[-1][1], e)
         else:
            ans.append([s, e])
      return ans
ob = Solution()
inv = [[2, 5],[4, 10],[20, 25]]
print(ob.solve(inv))

输入

[[2, 5],[4, 10],[20, 25]]

输出

[[2, 10], [20, 25]]

Arnab Chakraborty

更新日期：2020 年 11 月 19 日

746 次浏览

开启您的职业生涯

完成课程后获得认证

开始