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