Problem1078--[视频]动态规划入门(非常规DP2:不重叠线段)

1078: [视频]动态规划入门(非常规DP2:不重叠线段)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 2
[Status] [Submit] [Creator:]

Description

【问题描述】

n条线段(给出起点和末端),分别坐落在数轴上,要求它们之间彼此不重叠的条件下,最大可以覆盖数轴的长度。(数轴的长度指线段覆盖数轴数字的个数)(1~3和3~4的线段视为重叠)

【输入】

    第一行一个整数n(1<=n<=1000)

    2n+1行,每行两个整数start和end,描述线段的起点和末端,所有线段都落在[0,2000]的范围内。

【输出文件】

    一个整数,表示最多覆盖数轴的长度。

Sample Input Copy

3
1 3
7 8
3 4

Sample Output Copy

5

HINT

 

Source/Category