学校打算在周末办一个游园会。游园会包括n个游戏项目,每一个游戏项目分别在s_i时间开始,在 t_i 时间结束。对于每一个项目,你都可以选择是否参加,但是一旦参加了某个项目,你就必须完成,不得中途退出。此外,参加项目的时间不能重叠(即使是开始的瞬间和结束的瞬间的重叠也是不允许的)。
小明想要报名参加游园会,并且尽可能多的完成游园会的游戏项目,你可以帮助小明选择项目吗?
第一行为一个整数n,代表共有n个游戏项目;
第二行为n个整数,第 i 个数代表项目 i 开始的时间s_i,两个数之间使用空格分隔;
第三行为n个整数,第 i 个数代表项目 i 结束的时间t_i,两个数之间使用空格分隔。
输出数据为一行一个整数,表示小明最多可以选择多少个游戏项目。
5 1 2 4 6 8 3 5 7 9 10
3
对于100%的数据:1\leq N\leq 10^5,1\leq s_i\leq t_i\leq 10^9
时间限制 | 1 秒 |
内存限制 | 256 MB |