## 定義
對 $Q$ 的每個子問題都做出**當下的最優解**，從而期望此為 $Q$ 的最優解
這樣單看定義可能沒有什麼想法，這邊舉一個找錢的例子
如果一個店員需要找你 $67$ ，他最少需要幾個硬幣(硬幣只有 $1、5、10、50$)
對於找錢的例子來說，最優解就是用當下能給面額最大的硬幣去湊
找 $67$，可以用 $50$ 找一個硬幣，剩下 $17$，已經找了 $1$ 個硬幣
找 $17$，可以用 $10$ 找一個硬幣，剩下 $7$，已經找了 $2$ 個硬幣
找 $7$，可以用 $5$ 找一個硬幣，剩下 $2$，已經找了 $3$ 個硬幣
找 $2$，可以用 $1$ 找兩個硬幣，剩下 $0$，已經找了 $5$ 個硬幣

不過找錢有非常嚴格的定義，不是每個硬幣組合都可以用 Greedy 解
貪婪演算法也算是一種類似**人類的思考方式**，不過很多時候**不能**從大問題開始思考
而是要**一步步**地推進**小問題**，比如下面跑單的例子，你如果用**一整個大時間段**去思考
那就會用暴力的方式去**任意組合直到找到最優**，但如果只考慮前後兩個時間段的關係
那結果就會變成，"要盡量**留時間**去處理下一個事情" 的思考方式
這樣依序推理的方式也就是 Greedy 的其中一種求解方式 "堆答案"

## 選擇問題-外送跑單
這種題型是很經典的，都是像這樣**有時間範圍**的多個選擇，問怎麼選能跑過**最多**選擇
用外送當作舉例，每個單子都是**同樣的價格**，但是**處理時間不同**，問怎麼跑能拿**最多錢**
如果用枚舉(暴力)的方式，只有選跟不選，時間複雜度會達到 $O(2^n)$，但也是最直接的
當然現在的主題是 Greedy，所以就不把枚舉的過程跟做法拉出來說明
先舉個例子方便解析等等的作法，目前有四個單子，時間花費如下
如果用腦袋直接算也知道應該照: 單 $3$、單 $2$、單 $4$ 去跑才能有最多錢
當然大部分人在腦袋中還是用類似枚舉的方式去看，所以這裡先**排序**一下**找規律**
(這是根據結束時間前後排序的，只是剛好也對到開始時間而已)
一般人把想做更多活動，會做兩種行為
1. 在之後空閒時間排入活動
2. 在當前活動之間排入活動(在**已經確定**的活動中間插入**新的**活動)

但是這種題目**不會**遇到第二種情況，因為大部分都是從**完全沒有活動**開始規劃跑單行程
也就是說，只要確保現在這單跑完後的**空閒時間越多**，接下來能跑得單子應該就**越多**
因為單子時間本身是不變的，在下午 $2$ 點結束跟在早上 $8$ 結束，很明顯**後者剩餘時間多**
用上面的圖例去判斷，如果我在跑完單 $3$ 後選擇單 $1$ (結束時間晚)，那就剩下**一個時間段**
但是如果選擇單 $2$ (結束時間早)，就會剩**兩個時間段**，也多了一個單 $4$ 可以做後續的選擇
假設單 $4$ 也會跟單 $2$ 重疊到，那還是不影響這個原則，因為選單 $2$ 跟單 $1$ 的答案相同
所以最後可以總結出，找**結束時間越早**的單子就可以跑越多單
剩下就是注意**重疊**或是**題目給的小細節**等等

---
這裡剛好有一個相似的例題-[e576. 10020 - Minimal Coverage](https://zerojudge.tw/ShowProblem?problemid=e576)

給定多組線段坐標$[Li, Ri]$ (在 $X$ 軸上)
請選擇 "最少" 數量的線段，使得選擇的線段完全覆蓋 $[0, M]$
(假設 $M=1$，應選區段 $2$，線段數量為 $1$ )
題目解析 :
這題需求是完全覆蓋 $[0,M]$ 跟最少數量，很明顯完全覆蓋需要先被考慮
如果有兩種選擇，一個是**多組**小線段，另一個是大線段配小線段
* $[0,1]、[1,2]、[2,3]、...[M-3,M-2]、[M-2,M]$
* $[0,M-2]、[M-1,M+1]$

很明顯第 $2$ 種選擇並不能滿足需求，並且第 $1$ 種選擇也不是最優解
最優解應該是 $[0,M-2]、[M-2,M]$，只需要 $2$ 個線段就可以覆蓋 $[0,M]$

進一步把範圍縮小，假如有兩個選擇，$M = 4$
* $[0,1]、[1,2]、[1,3]、[3,4]$
* $[0,3]、[3,4]$

可能有人看出來了，我舉的例子都是先照**起點**排序，如果起點一樣就照**終點**排序
這樣做的好處是幫助思考，現在這個例子，回到原本 Greedy 的定義: **小問題最優解**
那要處理 $M = 4$，就要先考慮 $M = 1\sim3$，如果現在 $M = 1$，$[0,1]、[0,3]$ 都是最優解
如果現在 $M = 2$，最優解只有 $[0,3]$，$M = 3$ 時也一樣
所以應該可以總結成一個規律，要盡量找**能接合前面線段**並且**結尾越遠越好**的線段
能接合前面線段是為了滿足覆蓋 $[0,M]$ 的條件，結尾越遠越好是 Greedy 的展現
需要注意的是，能接合前面線段的意思有兩種
1. 剛好接合，例如 : $[1,2]、[2,5]$
2. 部分重疊接合 : $[1,4]、[2,9]$

因為已經有排序了，所以可以更方便的照順序找到新的線段並接上
最後要注意原本並沒有線段，所以假設一個線段是 $[0,0]$ 方便後面接上
以下是程式的執行順序跟總結
1. 輸入資料跟排序線段
2. 從舊線段去找新線段(要接合舊線段、結尾越遠越好) (註解:階段一)
3. 重複判斷哪個新線段更好(最好的叫 best 新線段) (註解:階段二)
5. 如果目前新線段起點已經超過舊線段結尾，將之前找到的 best 新線段**接到舊線段**上
6. 重複步驟 $2\sim 4$ 直到線段範圍至少覆蓋 $[0,M]$
7. 在步驟 $2\sim4$ 中如果找不到符合條件的新線段代表無法覆蓋 $[0,M]$ => 直接結束

最後記得同時記錄接上去的線段，因為輸出會用到(我是紀錄線段的 index )
以下是程式碼跟註解

#include<bits/stdc++.h>
using namespace std ;
#define P pair<int,int>
#define FF first
#define SS second

P ranges[100005] ; // 題目給定線段

bool cmp1(P a, P b) { // 先比較起點再比較終點
    if (a.FF == b.FF)
        return a.SS < b.SS ; // 由小到大
    return a.FF < b.FF ; // 由小到大
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;

    int m, t ;
    cin >> t ;
    while (t--) { // 共 t 次
        vector<int> rans ; // 答案線段index
        int num = 0, left, right ; ;
        // 題目給 num 個線段、線段左右數值
        cin >> m ;
        while (cin >> left >> right && (left || right)) {
            ranges[num] = {left, right} ;
            num++ ;
        }
        sort(ranges, ranges+num) ; // 自定義排序

        int idx = 0, max_right = 0, nright, nidx ;
        // 目前線段最右邊、階段 2 線段最右邊、階段 2 選出線段的index

        while (max_right < m) { // 階段 1
            bool have = false ;
            nright = 0, nidx = 0 ;
            while (idx < num) { // 階段 2
                if (ranges[idx].FF <= max_right) { // 可連接
                    have = true ;
                    if (ranges[idx].SS > nright) { // 新線段
                        nright = ranges[idx].SS ; // 階段 2 最右邊
                        nidx = idx ; // 紀錄新線段 index
                    }
                }
                else // 無符合條件新線段
                    break ;
                idx++ ;
            }
            if (!have) break ; // 找不到可連接的新線段(無法完全覆蓋)
            else {
                rans.push_back(nidx) ; // 紀錄新線段 index
                max_right = nright ; // 更新目前最右邊
            }
        }

        if (max_right >= m) { // 完全覆蓋 [0,m]
            cout << rans.size() << '\n' ; // 答案數量
            for (int it:rans) {            // 輸出答案線段
                cout << ranges[it].FF <<' '<< ranges[it].SS << '\n' ;
            }
        }
        else
            cout << "0\n" ; // 無法覆蓋
        cout << '\n' ;
    }

    return 0 ;
}