#P0037. 小未的活动安排

小未的活动安排

题目描述

作为未来教育的高材生,小未同学每天的日程都排的很满,然而在同一时间内小未只能参加一个活动,所以他不得不放弃一些他很想参加的活动。小未同学希望每天尽可能充实,所以他想找出一个可以参加最多活动的安排。

假设今天小未一共可以参加 nn 个活动,第 ii 个活动在 lil_i 时刻(包含第 lil_i 时刻)开始,在 rir_i 时刻(包含第 rir_i 时刻)结束。小未想知道他可以参加的最多活动的数目。显然,他不能同时参加两个活动。

输入格式

第一行一个整数 nn(1≤n≤10001 \leq n \leq 1000),今天小未一共可以参加的活动数目。 接下来的 nn 行,每行两个整数 lil_i 和 rir_i(1≤si≤fi≤2×1031 \leq s_i \leq f_i \leq 2 \times 10^3),表示第 ii 个活动的起始时间和终止时间。

输出格式

输出一行一个整数,表示小未今天可以参加的最多活动的数目。

样例 #1

样例输入 #1

4
1 3
4 6
2 5
1 7

样例输出 #1

2

样例解释

可以证明,当且仅当选择 {1,3}\{1,3\}、{4,6}\{4,6\} 两个互不冲突的活动,最终参加的总活动数目最多,为 22 个。