1. 區間調度
1.1. 題目
給定個區間，每個區間由開始時間
start和結束時間end表示。請選擇最多的互不重疊的區間，返回可以選擇的區間的最大數量。
輸入格式：
-
第一行包含一個整數n，表示區間的數量
-
接下來n行，每行包含兩個整數，分別表示區間的開始時間和結束時間
輸出格式：
-
一個整數，表示最多可以選擇的互不重疊的區間數量
示例輸入：
4
1 3
2 4
3 5
6 7示例輸出：
31.2. 思路
1. 理解問題：我們需要從給定的多個區間中選出盡可能多的區間，且這些區間之間沒有任何重疊部分。
2. 貪心算法思想：貪心算法在每一步選擇中都采取當前狀態下最優的選擇，從而希望導致全局最優的結果。對于區間調度問題，常見的貪心策略有：
-
最早開始時間
-
最早結束時間
-
最短區間長度
-
最少沖突區間
其中，"最早結束時間"策略被證明可以得到最優解。
3. 為什么選擇最早結束時間？
-
選擇一個結束早的區間，可以給后面留下更多的時間安排其他區間
-
這樣能最大化剩余可用時間，從而可能選擇更多區間
4. 算法步驟
-
將所有區間按照結束時間從小到大排序
-
初始化選擇的區間數量為0，記錄上一個選中區間的結束時間
-
遍歷排序后的區間：
-
如果當前區間的開始時間 >= 上一個選中區間的結束時間
-
則選擇當前區間，更新結束時間，計數+1
-
-
返回最終的計數結果
5. 時間復雜度
-
排序：O(n log n)
-
遍歷：O(n)
-
總時間復雜度：O(n log n)
1.3. 代碼
# 讀取輸入
n = int(input()) # 區間數量
intervals = []
for _ in range(n):start, end = map(int, input().split())intervals.append([start, end])"""
計算最多可以選擇的互不重疊的區間數量
參數:intervals: 區間列表，每個區間表示為[start, end]
返回:最多可以選擇的互不重疊的區間數量
"""
# 特殊情況處理：如果沒有區間或只有一個區間
if not intervals:print(0)
if len(intervals) == 1:print(1)
# 1. 按照區間的結束時間進行升序排序
# 這樣我們可以優先選擇結束早的區間
)
 對比)
)
