数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找区间列表中最长区间的长度
假设我们有一个区间列表，每个区间都以[起始, 结束]的形式表示。我们需要找到通过合并任意数量的重叠区间可以形成的最长区间。
因此，如果输入类似于[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]，则输出为9，因为合并后，我们得到长度为9的区间[1, 9]。
为了解决这个问题，我们将遵循以下步骤：
- 对区间列表进行排序
- union := 区间列表中的第一个区间
- best := union[结束] - union[起始] + 1
- 对于区间列表中除第一个区间外的每个起始时间s和结束时间e，执行以下操作：
- 如果 s <= union[结束]，则
- union[结束] := union[结束] 和 e 的最大值
- 否则，
- union := 一个新的区间 [s, e]
- best := best 和 union[结束] - union[起始] + 1 的最大值
- 如果 s <= union[结束]，则
- 返回 best
让我们来看下面的实现来更好地理解：
示例
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
更新于：2020年11月19日
415 次浏览
广告