题目描述
设有
n
个活动的集合 E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动
i
都有一个要求使用该资源的起始时间 s
i
和一个结束时间 fi
，且 si
。如果选择了活动
i
，则它在时间区间[si
,fi
) 内占用资源。若区间 [si
,fi
) 与区间[sj
,fj
) 不相交，则称活动
i
与活动
j
是相容的。也就是说，当fi
≤sj
或 fj
≤si
时，活动
i
与活动
j
相容。选择出由互相兼容的活动组成的最大集合。
输入
第一行一个整数
n
；
接下来的
n
行，每行两个整数 si
和 fi
。
输出
输出互相兼容的最大活动个数。
样例输入
4
1 3
4 6
2 5
1 7
样例输出
2
提示
数据范围与提示
1≤n≤1000
来源/分类
ybttg 贪心