一、題目介紹

• 活動安排

題目描述
給定 $n$ 個活動，每個活動的時間區間為 $[a_i,b_i)$（左閉右開）。要求選擇盡可能多的活動，使得這些活動的時間區間互不重疊。

輸入描述

• 第一行：整數 $n$（$1\le n\le 2\times 10^5$），表示活動數量
• 后續 $n$ 行：每行兩個整數 $a_i,b_i$（$0\le a_i<b_i\le 10^9$）

輸出描述

• 一個整數，表示最多可選擇的活動數

示例

• 輸入：

  3
  1 4
  1 3
  3 5
  

• 輸出：2
• 說明：可選擇活動 $[1,3)$ 和 $[3,5)$

二、解題思路

2.1 核心問題

在多個時間區間中選出最大互斥子集——經典的區間調度問題。

2.2 貪心策略

1. 排序策略

   • 將所有活動按結束時間升序排序
   • 結束時間相同時，開始時間不影響結果（可任意排序）

2. 選擇策略

   • 初始化選擇第一個活動（最早結束）
   • 遍歷后續活動：
     • 若當前活動的開始時間 $\ge$ 上一個選中活動的結束時間
     • 則選擇該活動，并更新記錄點

2.3 正確性證明

• 貪心選擇性：最早結束的活動一定在某個最優解中
• 最優子結構：選擇最早結束活動后，剩余問題仍是相同結構的子問題
• 反證法：若存在更優解，其第一個活動結束時間一定不早于貪心選擇的活動

三、算法分析

3.1 為什么按結束時間排序？

排序方式	反例	問題原因
按開始時間排序	[1,5] [2,3] [4,6]	選 [1,5] 后無法選其他
按區間長度排序	[1,4] [2,3] [3,5]	選最短 [2,3] 后只能再選一個
按結束時間排序	無反例	保證最大化剩余時間

3.2 復雜度分析

• 時間復雜度：$O(n\log n)$
  • 排序：$O(n\log n)$（占主導）
  • 遍歷：$O(n)$
• 空間復雜度：$O(n)$
  • 存儲 $n$ 個活動對象

3.3 算法流程圖解

flowchart TDA[開始] --> B[讀取活動數量n]B --> C[創建空活動列表]C --> D[循環讀取n個活動]D --> E[存儲活動到列表]E --> F{是否讀完n個活動？}F -- 否 --> DF -- 是 --> G[按結束時間升序排序]G --> H[初始化：count=0, lastEnd=-1]H --> I[遍歷排序后活動列表]I --> J{當前活動開始時間 ≥ lastEnd？}J -- 是 --> K[count++，更新lastEnd=當前結束時間]J -- 否 --> L[跳過該活動]K --> M{是否還有活動？}L --> MM -- 是 --> IM -- 否 --> N[輸出count]N --> O[結束]

3.3.1 流程圖說明

1. 數據讀取階段：

   • 讀取活動數量 n
   • 循環讀取 n 個活動的時間區間
   • 存儲在 ArrayList 中

2. 排序階段：

   • 使用自定義比較器 ActivityComparator
   • 按結束時間升序排序（最早結束的在前）

3. 貪心選擇階段：

   flowchart LRP[lastEnd初始值-1] --> Q{遍歷活動}Q --> R[活動A: start≥lastEnd?]R -- 是 --> S[選擇A, count+1, lastEnd=A.end]R -- 否 --> T[跳過A]S --> U{繼續遍歷}T --> U
   

4. 選擇邏輯示例（輸入 [[1,4], [1,3], [3,5]]）：

   flowchart TBsubgraph 排序后A1[活動2: 1-3] --> A2[活動1: 1-4] --> A3[活動3: 3-5]endA1 --> B1{1 ≥ -1?} -- 是 --> C1[選擇, count=1, lastEnd=3]C1 --> A2A2 --> B2{1 ≥ 3?} -- 否 --> C2[跳過]C2 --> A3A3 --> B3{3 ≥ 3?} -- 是 --> C3[選擇, count=2, lastEnd=5]
   

3.3.2 關鍵步驟說明

1. 排序意義：

   • 結束時間最早的活動優先被選擇
   • 為后續活動留下最大時間窗口

2. lastEnd初始值-1的作用：

   • 確保第一個活動總是被選擇
   • 數學上滿足：任意開始時間 ≥ -1

3. 選擇條件 start ≥ lastEnd：

   • 嚴格保證活動時間不重疊
   • 充分利用左閉右開區間特性（[1,3) 和 [3,5) 可銜接）

此流程圖清晰展示了貪心算法的核心思想：通過結束時間排序最大化剩余時間窗口，通過順序遍歷實現高效選擇。

四、模擬演練

輸入數據

3
1 4
1 3
3 5

執行流程

1. 排序階段（按結束時間升序）：

   原始順序	開始時間	結束時間
   活動1	1	4
   活動2	1	3
   活動3	3	5

   ↓ 排序后 ↓

   新順序	開始時間	結束時間
   活動2	1	3
   活動1	1	4
   活動3	3	5

2. 選擇階段：

   當前活動	開始時間	結束時間	上一活動結束時間	是否選擇	已選活動數	更新結束時間
   活動2	1	3	-1 (初始)	?	1	3
   活動1	1	4	3	?（1 < 3）	1	3
   活動3	3	5	3	?（3 ≥ 3）	2	5

3. 輸出結果：2

邊界測試

• 全重疊活動：
  輸入：[1,2), [1,2), [1,2)
  輸出：1（只能選一個）

• 大范圍數據：
  輸入：$2\times 10^5$ 個 $[i,i+1)$ 區間
  輸出：$2\times 10^5$（所有活動互不重疊）

五、完整代碼

import java.util.*;/*** 活動類：表示一個活動的時間區間 [startTime, endTime)*/
class Activity {int startTime;  // 活動開始時間int endTime;    // 活動結束時間（不包含）// 構造函數Activity(int startTime, int endTime) {this.startTime = startTime;this.endTime = endTime;}
}/*** 活動比較器：按結束時間升序排序* 為什么按結束時間排序？因為結束時間決定了活動占用時間段的長度*/
class ActivityComparator implements Comparator<Activity> {@Overridepublic int compare(Activity a, Activity b) {// 按結束時間從小到大排序：最早結束的排前面return a.endTime - b.endTime;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 1. 讀取活動數量int n = in.nextInt();// 2. 創建活動列表并存儲所有活動List<Activity> activities = new ArrayList<>();for (int i = 0; i < n; i++) {int startTime = in.nextInt();int endTime = in.nextInt();activities.add(new Activity(startTime, endTime));}// 3. 關鍵步驟：按結束時間升序排序（貪心算法的核心）Collections.sort(activities, new ActivityComparator());// 4. 貪心選擇過程int count = 0;          // 記錄可安排的活動數量int lastEndTime = -1;   // 上一個被選中活動的結束時間（初始化為-1，表示尚未選擇任何活動）for (Activity activity : activities) {// 如果當前活動開始時間 ≥ 上一個活動的結束時間（說明時間不重疊）if (activity.startTime >= lastEndTime) {count++;  // 選擇不重疊的活動lastEndTime = activity.endTime;  // 更新最后一個活動的結束時間}}// 5. 輸出結果System.out.println(count);}
}

關鍵優化點

1. 結束時間排序

   Collections.sort(activities, (a, b) -> a.endTime - b.endTime);
   

2. 貪心選擇

   if (act.startTime >= lastEnd) {count++;lastEnd = act.endTime;
   }
   

為什么不用優先隊列？

• 排序后只需一次線性遍歷，復雜度 $O(n)$
• 優先隊列 $O(n\log n)$ 的插入/刪除反而增加開銷

通過結束時間排序+貪心遍歷，高效解決大規模區間調度問題