数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：查找播放所有电影所需的最少影院数量
假设我们有一系列表示不同电影放映时间的区间（可能重叠），我们需要找到播放所有电影所需的最少影院数量。
例如，如果输入区间为 intervals = [[20, 65],[0, 40],[50, 140]]，则输出为 2，因为[20, 65]和[0, 40]重叠，[20, 65]和[50, 140]也重叠，但[0, 40]和[50, 140]不重叠。因此我们需要2个影院。
为了解决这个问题，我们将遵循以下步骤：
- t := 新列表
- 对于 intervals 中的每个区间 [a, b]，执行：
- 在 t 的末尾插入 [a, 1]
- 在 t 的末尾插入 [b, -1]
- ans := 0, count := 0
- 对于排序后的 t 中的每个对 (x, d)，执行：
- count := count + d
- ans := ans 和 count 的最大值
- 返回 ans
让我们来看下面的实现，以便更好地理解。
示例代码
class Solution: def solve(self, intervals): t = [] for a, b in intervals: t.append((a, 1)) t.append((b, -1)) ans = count = 0 for x, d in sorted(t): count += d ans = max(ans, count) return ans ob = Solution() intervals = [[20, 65],[0, 40],[50, 140]] print(ob.solve(intervals))
输入
[[20, 65],[0, 40],[50, 140]]
输出
2
更新于：2020年11月25日
234 次浏览
广告