问题 4843 --4.食堂打菜

4843: 4.食堂打菜

题目描述

  小明提供 $B$ 个区间的清单。一个区间是一对整数 $start$$end$,表示一些连续的食堂窗口,比如 $1-3,7-8,3-4$ 等等。小明可以任意选择区间,但是他选择的区间不能有重叠。
在上面的例子中,$1-3$ 和 $3-4$ 是重叠的。聪明的你应该选择 $1-3,7-8$,这样可以吃到 $5$ 个窗口里的东西。
现在给出一些区间,请你编程帮助小明找一些区间,使他能吃到最多的东西。

输入

第一行为一个整数 B 。
第 $2$ 到 $B$ 行,每行两个整数 $start$$end$,表示一个区间,保证较小的端点在前面。

输出

一行一个整数,表示小明最多能吃到多少个窗口里的食物。

样例输入输出

输入#1 复制
3 
1 3 
7 8 
3 4 
输出#1 复制
5

提示

对于 $20\%$ 的数据,满足 $ 1 \leq B \leq 10$;
对于 $50\%$ 的数据,满足 $ 1 \leq B \leq 200$;
对于 $100\%$ 的数据,满足 $ 1 \leq N \leq 2000, 1 \leq B \leq 1000,  1\leq start \leq end \leq N $ 。

序号 标题 作者 发表时间 费用 订购数 操作