最近在刷算法題時，又遇到了一道非常經典的貪心題目：給定若干閉區間，求最少需要多少個點，使得每個區間至少包含一個點。這道題看似簡單，卻完美展現了貪心策略的用處。
問題描述
輸入：
\(n\) 個閉區間 \([l_i, r_i]\)（\(1 \le i \le n\)）
輸出：
最少需要放置多少個點，使得每個區間都至少包含一個點。
例如：
區間：[1,3], [2,5], [4,6]
答案：2（比如在點3和點6處放置）
我的解法：右端點優先，貪心選點
核心思想：
把所有區間按右端點從小到大排序，然後儘可能“晚”地放點——也就是放在當前區間的右端點上。
為什麼這樣做？
你希望一個點能覆蓋儘可能多的後續區間。那麼，越靠右放，越容易“錯過”後面的區間；而越靠左放，又可能浪費了覆蓋能力。
但如果我們在當前未被覆蓋的區間中，選擇右端點最小的那個，並把點放在它的右端點上，就能保證這個點“剛好”覆蓋它，同時最大化對後續區間的潛在覆蓋能力。
代碼實現（C++）
#include <bits/stdc++.h>
using namespace std;
struct Interval {
int left, right;
};
bool cmp(const Interval& a, const Interval& b) {
return a.right < b.right; // 按右端點升序
}
int main() {
int n;
cin >> n;
vector<Interval> intervals(n);
for (int i = 0; i < n; ++i) {
cin >> intervals[i].left >> intervals[i].right;
}
sort(intervals.begin(), intervals.end(), cmp);
int pointCount = 0;
int lastPoint = -1; // 上一個放置的點
for (int i = 0; i < n; ++i) {
// 如果當前點沒被覆蓋
if (lastPoint < intervals[i].left) {
lastPoint = intervals[i].right; // 在右端點放新點
pointCount++;
}
}
cout << pointCount << endl;
return 0;
}💡 小提示：判斷條件只需
lastPoint < left即可。因為lastPoint始終是非遞減的（我們總是往右放點），不可能出現lastPoint > right的情況。
為什麼貪心是對的？
要證明貪心算法的正確性，通常需要兩個關鍵性質：
- 貪心選擇性質（Greedy Choice Property）
存在一個最優解，其中第一個點就放在右端點最小的區間的右端點上。
證明思路：
假設最優解中第一個點 \(p\) 覆蓋了第一個區間 \([l_1, r_1]\)，那麼 \(p \in [l_1, r_1]\)。
如果我們把 \(p\) 改成 \(r_1\)，會發生什麼？
它依然覆蓋 \([l_1, r_1]\)；
對於其他被 \(p\) 覆蓋的區間 \([l_j, r_j]\)，由於我們按 \(r\) 排序，有 \(r_j \ge r_1\)；
又因為 \(p \ge l_j\) 且 \(p \le r_1\)，所以 \(l_j \le r_1 \le r_j\)，即 \(r_1\)
因此，把點移到 \(r_1\)
- 最優子結構（Optimal Substructure）
一旦我們在 \(r_1\) 放了一個點，所有包含 \(r_1\)
複雜度分析
排序：\(O(n \log n)\)
遍歷選點：\(O(n)\)
總時間複雜度：\(O(n \log n)\)
空間複雜度：\(O(n)\)（存儲區間）
效率非常高，適用於大規模數據。
我對貪心算法的理解
貪心算法常常被初學者誤解為“隨便選看起來好的”，但實際上，貪心是一種需要嚴格證明的策略。
它的魅力在於簡潔高效——沒有回溯、沒有狀態記憶，一步到位；直覺友好——很多貪心策略符合人類的“局部最優”直覺；適用性強——在區間問題、圖論（如最小生成樹）、編碼（霍夫曼）等領域大放異彩。
比如本題如果按左端點排序，或者在左端點放點，就可能得到次優解。貪心的正確性必須通過數學證明來支撐，而不是靠測試樣例“蒙對”。
總結
區間選點問題是一個經典的貪心模型；
關鍵策略：按右端點排序 + 在右端點放點；
正確性由貪心選擇性質和最優子結構共同保證；
時間複雜度 \(O(n \log n)\)，實用且優雅。
