#P0037. 小未的活动安排
小未的活动安排
题目描述
作为未来教育的高材生,小未同学每天的日程都排的很满,然而在同一时间内小未只能参加一个活动,所以他不得不放弃一些他很想参加的活动。小未同学希望每天尽可能充实,所以他想找出一个可以参加最多活动的安排。
假设今天小未一共可以参加 个活动,第 个活动在 时刻(包含第 时刻)开始,在 时刻(包含第 时刻)结束。小未想知道他可以参加的最多活动的数目。显然,他不能同时参加两个活动。
输入格式
第一行一个整数 (),今天小未一共可以参加的活动数目。 接下来的 行,每行两个整数 和 (),表示第 个活动的起始时间和终止时间。
输出格式
输出一行一个整数,表示小未今天可以参加的最多活动的数目。
样例 #1
样例输入 #1
4
1 3
4 6
2 5
1 7
样例输出 #1
2
样例解释
可以证明,当且仅当选择 、 两个互不冲突的活动,最终参加的总活动数目最多,为 个。