【错题集-编程题】活动安排（贪心 - 区间）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> PII;
vector<PII> q;
 
bool cmp(PII x, PII y)
{
    return x.second<y.second;
}
 
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        q.push_back({a, b});
    }
    sort(q.begin(), q.end(), cmp);
    int cnt=1;
    int ed=q[0].second;
    for(int i=1; i<q.size(); i++)
    {
        if(ed<=q[i].first)
        {
            cnt++;
            ed=q[i].second;
        }
    }
    cout << cnt << endl;
    return 0;
}

//写法一
#include <iostream>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 2e5 + 10;
 
int n;
PII arr[N];
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i].first >> arr[i].second;
    sort(arr, arr + n);
 
    int ret = 0, r = arr[0].second;
    for(int i = 1; i < n; i++)
    {
        if(arr[i].first < r) // 有重叠
        {
            r = min(r, arr[i].second);
        } 
        else // 没有重叠
        {
            ret++;
            r = arr[i].second;
        }
    }
    cout << ret + 1 << endl;
 
    return 0;
}
 
//写法二
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=2e5+10;
 
struct activity
{
    int a;
    int b;
    static bool cmp(const activity& v1, const activity& v2)
    {
        return v1.b<v2.b;
    }
}ac[N];
 
int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++)
        cin >> ac[i].a >> ac[i].b;
    sort(ac, ac+n, activity::cmp);
    int cnt=1;
    int ed=ac[0].b;
    for(int i=1; i<n; i++)
    {
        if(ed<=ac[i].a)
        {
            cnt++;
            ed=ac[i].b;
        }
    }
    cout << cnt << endl;
    return 0;
}