NYoj 891 - 區間貪心：最少點覆蓋所有區間

問題描述

給定 N 個閉區間 [L, R]，選取最少數量的點，使每個區間至少包含一個選取的點。輸出最少點數。

貪心策略：按右端點升序排序

1. 將所有區間按 R 升序排序 (R 相同按 L 降序)。
2. 初始化 ans = 0, last_selected = -∞。
3. 遍歷排序後的區間：
   • 若 last_selected < L (當前點不覆蓋該區間)，則選取 R 作為新點：last_selected = R, ans++。
   • 否則當前點已覆蓋該區間，跳過。

正確性證明

• 考慮最優解中最右端的點。若不在某區間的右端點，可右移至右端點不減少覆蓋範圍。
• 按右端點排序，貪心選取最早結束區間的右端點，為後續區間留出最大空間。
• 經典「區間調度 / 點覆蓋」問題，貪心證明可參考教科書 (如《算法導論》)。

參考代碼

#include 
using namespace std;

struct Interval { int l, r; };

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        vector a(n);
        for (int i = 0; i < n; i++) {
            int x, y; scanf("%d%d", &x, &y);
            a[i].l = min(x, y);
            a[i].r = max(x, y);
        }
        sort(a.begin(), a.end(), [](const Interval& A, const Interval& B) {
            return A.r != B.r ? A.r < B.r : A.l > B.l;
        });
        int ans = 0;
        int last = -1e9;
        for (auto& seg : a) {
            if (last < seg.l) {
                last = seg.r;
                ans++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

樣例演示

Input:
4
1 5
2 4
1 4
2 3
3
1 2
3 4
5 6
1 2

Output:
1
3
1

第一組：區間 [2,3] 最早結束，選 3 覆蓋所有。
第二組：三個不相交區間，各需一點。
第三組：單區間需 1 點。

複雜度

• 排序 O(N log N)。
• 掃描 O(N)。
• 空間 O(N)。

變體擴展

• 若需輸出具體選取點位置，記錄 last 即可。
• 若區間為開區間/半開區間，邏輯類似，注意邊界判斷。
• 加權版本 (每個點有代價) 需 DP 或最小費用流。