活动安排

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;
}
上一篇:Secret Message 秘密信息


下一篇:Phone List