活动安排

https://loj.ac/problem/10000

题目描述

  在时间轴上，有(n)条线段，起点为(s_i)，终点为(f_i)，求最多选取多少条线段使其两两互不相交。不过注意这里的区间为一段闭，一段开，可直接用贪心。

思路

　　我们先考虑将(n)条线段按右端点升序序排序，若右端点相同则按左端点升序排序（其实左端点无所谓）。那么，我们只需升序查找判断当前线段能放入即可，若可以，则(ans++)，否则就继续循环。这个贪心策略显然是对的，因为我们如果能选择当前([si,fi),[sj,fj)) ((fi<fj))这两条线段，那么我们可以选择第一条线段，这样对后续状态影响最小，并且肯定可以选，这样必定会是最优情况下的方案之一。

代码

#include <bits/stdc++.h>
using namespace std;
struct aa
{
    int st,ed;
}a[1100];
bool cmp(aa x,aa y)
{
    if(x.ed!=y.ed)return x.ed<y.ed;
    else return x.st<y.st;
}
int main() 
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&a[i].st,&a[i].ed);
    sort(a,a+n,cmp);
    int ans=0,k=0;
    for(int i=0;i<n;i++)
        if(a[i].st>=k)
        {
            k=a[i].ed;
            ans++;
        }
    printf("%d",ans);
    return 0;
}