学步园

57、求最大重叠区间大小
题目描述：请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠
区间的大小。对一个正整数  n  ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B）
之间，即 A<=n<=B 或 A>=n>=B  ，则  n  属于该行；
如果  n  同时属于行 i 和 j  ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整
数个数。 
例如，行（10 20）和（12 25）的重叠区间为  [12 20]  ，其大小为 9，行(20 10)和（  20 30  ）
的重叠区间大小为  1  。 

/*
57、求最大重叠区间大小
题目描述：请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠
区间的大小。对一个正整数  n  ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B）
之间，即 A<=n<=B 或 A>=n>=B  ，则  n  属于该行；
如果  n  同时属于行 i 和 j  ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整
数个数。 
例如，行（10 20）和（12 25）的重叠区间为  [12 20]  ，其大小为 9，行(20 10)和（  20 30  ）
的重叠区间大小为1 。

是每2行的最大重叠区间，不是所有的 
做法： 
将输入的区间按起点从小到大排列，然后对每个区间判断从当前区间起点到目前的end的距离，
此距离即为覆盖距离，当覆盖距离大于最大的距离时则更新最大距离。
每次循环都要判断是否需要更新end，end表示目前所有区间的最大终点值。
*/

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 100

struct node{
	int l,r;
};
node map[N];

bool cmp(node a,node b)
{
	return a.l<b.l;
}

int maxCover(node map[],int n)
{
	int i,end,left,right,len,maxLen;
	sort(map,map+n,cmp);//排序 
	end=map[0].r;
	maxLen=-1;//保存最大长度 
	for(i=1;i<n;i++)
	{
		left=map[i].l;//左 
		right=min(map[i].r,end);//右 
		if(left<=right)
			len=right-left+1;
		else
			len=0;
		if(len>maxLen)
			maxLen=len;
		if(map[i].r>end)//更新end 
			end=map[i].r;
	}
	return maxLen;
}

int main()					
{							 
	int n,i,a,b;
	while(1)
	{
		printf("请输入行数n（0结束）\n");
		scanf("%d",&n);
		if(n==0) break;
		for(i=0;i<n;i++)
		{
			scanf("%d%d",&a,&b);
			if(a<b)
			{
				map[i].l=a;
				map[i].r=b;	
			}
			else
			{
				map[i].r=a;
				map[i].l=b;
			}
		}
		printf("%d\n",maxCover(map,n));
	} 
	return 0;
}
/*
2
12 20
12 25
2
20 10
20 30
2
20 10
12 18
3
10 15
12 19
8 13
0
*/