「一本通 1.1 例 1」活动安排
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
设有 个活动的集合 ,其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动 都有一个要求使用该资源的起始时间 和一个结束时间 ,且 。如果选择了活动 ,则它在时间区间 内占用资源。若区间 与区间 不相交,则称活动 与活动 是相容的。也就是说,当 或 时,活动 与活动 相容。选择出由互相兼容的活动组成的最大集合。
输入格式
第一行一个整数 ;
接下来的 行,每行两个整数 和 。
输出格式
输出互相兼容的最大活动个数。
样例
4
1 3
4 6
2 5
1 7
2
数据范围与提示