返回小组 开始 2019-10-01 13:00:00

201909月赛(提高组)

结束 2019-10-01 17:00:00
Contest is over.
当前 2024-11-22 09:39:20

A. 【王码编程】九月月赛(提高组)——小明的培训班

描述

暑假开始了,小明的妈妈准备给小明报名一个课外培训班。但是现在的课外培训班太多了,小明的妈妈现在不知道该怎么选了,你能帮帮他吗?

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^51\leq s_i\leq t_i\leq 10^9


Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交