資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告