给你很多段线段,每段线段都有一个起始点si和和长度li。如果两段线段有部分重叠,则称这两段线段相互覆盖。比如si=4,li=4,sj=5,lj=5,第i段线段的覆盖区间为[4,8],第j段线段的覆盖区间为[5,10],二者可以连接成[4,10]的线段。再比如si=4,li=2,sj=7,lj=3,第i和j段线段覆盖区间分别为[4,6]、[7,10],两个区间是分隔开的。
现在给定一组线段,问最大的覆盖区间有多大?
第一张为一个正整数n,表示有n段线段。 第2至n+1行,每行为两个正整数si和li,表示第i段线段的起始点和长度。
最大(长)覆盖区间。
3 4 4 5 5 1 2
6
2 4 2 7 3
3
对100%的数据,1≤n≤100,0≤si,li≤100000。
时间限制 | 1 秒 |
内存限制 | 128 MB |