暑假开始了,小明的妈妈准备给小明报名一个课外培训班。但是现在的课外培训班太多了,小明的妈妈现在不知道该怎么选了,你能帮帮他吗?
有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 秒 |
内存限制 | 128 MB |