写个贪心题解吧

题目描述

略。。。

算法

硬核贪心

先读入，用一个pair二元组存，第一维存l，第二维存r。再排序。

排完序后，顺次遍历。

每次遍历时判断当前的l（即a[i].frist）和之前的r

小于等于就合并此时ans不变

大于就说明无法合并，那就ans++

注意代码是先处理了a[1]同时ans初值附为1

总之，很基础。。

时间复杂度

排序：O(n logn)
遍历：O(n)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int Max=100005;
pair<int,int>a[Max];
int n;
int ans=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        a[i]=make_pair(l,r);
    }
    sort(a+1,a+1+n);
    int r;
    r=a[1].second;
    ans++;
    for(int i=2;i<=n;i++)
    {
        if(a[i].first>r)
            ans++;
        if(a[i].second>r)
            r=a[i].second;
    }
    printf("%d",ans);
    return 0;
}

嗯，就是这么短。