CSES – Movie Festival

題目連結

題意

給你 n 個電影的開始和結束時間，問最多可以看幾個電影?
(一個時間只能看一個電影，結尾跟開頭可以是同時的，例如 3 5, 5 6 的話可以都看)

解題方法

每次都貪心的選取結束時間最早的電影來看我們就可以得到最好的結果。
每次都選結束最早的電影的話，就可以最大化我們之後可以選的電影的範圍 (因為結束比較早)。
這個greedy詳細證明的部分在吳邦一教授的 AP325 (4.2.2)單元中有提到。

其他錯誤的greedy想法及會錯的測資:

1. 選最早開始的電影

3
1 5
2 3
4 5

2. 選最短的電影

3
1 5
4 7
6 12

正確greedy程式碼 (選最早結束的)

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <pair<int,int> > a(n);
    //first = 右 second = 左
    for(int i = 0;i < n;i++){
        cin >> a[i].second >> a[i].first;
    }
    
    sort(a.begin(), a.end());
    int cur = 0;
    long long ans = 0;
    for(int i = 0;i < n;i++){
        if(a[i].second >= cur){
           cur = a[i].first;
           ans++;
        }
    }
    cout << ans << '\n';
}