# greedy 經典問題
主要說一些greedy的經典問題
=_=
## 排程問題/活動選擇問題（activity selection problem）
例題
https://judge.tcirc.tw/ShowProblem?problemid=d045
給一些活動的起始跟結束時間
問最多可參加到的活動數為多少個
### 講解
其實可以換一個方式理解題目:
**如何在數線上找到最多條不重疊的線段**

感覺就是找最短的
其實不是
會有假解的

但是想法換成這樣:
**如果有一個線段的右端點(右界)是現有線段裡面最小的(最左邊)，則最優解裡面一定會有這個線段**
這有點抽象
用筆畫畫看就會有感覺

**那就找右端點最小的(結束時間小的排到結束時間大的/最早結束就排前面)**
->排序!

**一句話總結:<font color="##FF0000">先結束的排在前面</font>**
看範例比較好理解
### 範例練習
AP325:d045: 例題 P-4-4. 幾場華山論劍activity selection
https://judge.tcirc.tw/ShowProblem?problemid=d045)
解1:用pair AC(23ms, 3.9MB)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<pair<int,int>>vec;            //紀錄活動開始時間跟結束時間
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int start,finish;                
        cin>>start>>finish;                        
        vec.push_back({finish,start});   //小心 pair的排序是先排begin()再排end()->begin()放結束時間，end()放開始時間
    }
    sort(vec.begin(),vec.end());         //排序找右端點(結束時間)最小的
    int finish_time=vec[0].first;        //找結束最早的，finish_time是更新目前參加的活動中最晚的結束時間
    int cnt=1;                           //不論如何至少有一個
    for(auto a:vec){  
        if(a.second>finish_time){        //剩下活動中的開始時間至少要超過finish_time　
            cnt++;                    
            finish_time=a.first;         //更新剩下活動的開始時間的下限
        }
    }
    cout<<cnt;
}

解1.5: AC(23ms, 3.9MB)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    
    vector<pair<int,int>>vec;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int start,finish;
        cin>>start>>finish;
        vec.push_back({finish,start});
    }
    sort(vec.begin(),vec.end());
    int finish_time=-1;             //這裡變-1
    int cnt=0;                      //這裡變0
    for(auto a:vec){
        if(a.second>finish_time){
            cnt++;
            finish_time=a.first;
        }
    }
    cout<<cnt;
}

解2:用struct AC(22ms, 1.8MB)
我是覺得不要啦
沒那麼好用
而且很醜
(也可能是我寫很醜)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007

struct act{
    int start,finish;
}vec[maxn];

bool cmp(act a,act b){
    return a.finish<b.finish;
}

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>vec[i].start>>vec[i].finish;
    }
    sort(vec,vec+n,cmp);
    int finish_time=vec[0].finish;
    int cnt=1;
    for(int i=1;i<n;i++){
        if(vec[i].start>finish_time){
            cnt++;
            finish_time=vec[i].finish;
        }
    }
    cout<<cnt;
}

洛谷:P1803 凌乱的yyy/线段覆盖
https://www.luogu.com.cn/problem/P1803

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007

signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<pair<int,int>>vec;
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int start,finish;
        cin>>start>>finish;
        vec.push_back({finish,start});
    }
    sort(vec.begin(),vec.end());
    int finish_time=vec[0].first;
    int cnt=1;
    for(auto a:vec){
        if(a.second>=finish_time){    //這題要用等於!
            cnt++;
            finish_time=a.first;
        }
    }
    cout<<cnt;
}