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

201909月赛(提高组)

结束 2019-10-01 17:00:00
Contest is over.
当前 2025-6-19 12:53:24

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

描述

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

nn个培训班,每一个培训班分别在sis_i时间开始,在tit_i时间结束。对于每一个培训班,你都可以选择是否参加。但是一旦报了某个培训班,你就必须全程参加,不得中途推出。此外,参加培训班的时间不能重叠(即使是开始的瞬间和结束的瞬间的重叠也是不允许的)。

你的任务是帮助小明的妈妈选择尽可能多的培训班。

输入

输入数据共有三行;

第一行为一个整数nn,代表共有nn个培训班;

第二行为nn个整数,第ii个数代表任务ii开始的时间sis_i,两个数之间使用空格分隔;

第三行为nn个整数,第ii个数代表任务ii结束的时间tit_i,两个数之间使用空格分隔。

输出

输出数据为一行一个整数,表示小明的妈妈最多可以选择多少个培训班。

样例

输入
复制

5
1 2 4 6 8
3 5 7 9 10

输出
复制

3

提示

数据规模:

对于100%的数据:1 N 1051\leq N\leq 10^51 si ti 1091\leq s_i\leq t_i\leq 10^9


Submit

登录

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