1 題目描述：請編寫程序，找出下面 “ 輸入數(shù)據(jù)及格式 ” 中所描述的輸入數(shù)據(jù)文件中最大重疊區(qū)間的大小。
對一個(gè)正整數(shù) n ，如果 n 在數(shù)據(jù)文件中某行的兩個(gè)正整數(shù)（假設(shè)為 A 和 B ）之間，即 A<=n<=B 或 A>=n>=B ，則 n 屬于該行；如果 n 同時(shí) 屬于行 i 和 j ，則 i 和 j 有重疊區(qū)間；重疊區(qū)間的大小是同時(shí)屬于行 i 和 j 的整數(shù)個(gè)數(shù)。
例如，行（ 10 20 ）和（ 12 25 ）的重疊區(qū)間為 [12 20] ，其大小為 9 ；行（ 20 10 ）和（ 12 18 ）的重疊區(qū)間為 [10 12] ，其大小為 3 ；行 (20 10) 和（ 20 30 ）的重疊區(qū)間大小為 1 。
輸入數(shù)據(jù)：程序讀入已被命名為 input.txt 的輸入數(shù)據(jù)文本文件，該文件的行數(shù)在 1 到 1,000,000 之間，每行有用一個(gè)空格分隔的 2 個(gè)正整數(shù)，這 2 個(gè)正整數(shù)的大小次序隨機(jī)，每個(gè)數(shù)都在 1 和 2^32-1 之間。（為便于調(diào)試，您可下載測試 input.txt 文件，實(shí)際運(yùn)行時(shí)我們會(huì)使用不同內(nèi)容的輸入文件。）
輸出數(shù)據(jù)：在標(biāo)準(zhǔn)輸出上打印出輸入數(shù)據(jù)文件中最大重疊區(qū)間的大小，如果所有行都沒有重疊區(qū)間，則輸出 0 。
評分標(biāo)準(zhǔn)：程序輸出結(jié)果必須正確，內(nèi)存使用必須不超過 256MB ，程序的執(zhí)行時(shí)間越快越好。
2 #include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;
typedef struct {int x,y,l;} Sec;
const int MAXN= 1000003;
int n,l;
Sec sec[MAXN];
int cmp(const void *a,const void *b)
{
return (*((Sec *)a)).x-(*((Sec *)b)).x;
}
int main()
{
int i,j,k,t;
freopen("input.txt","r",stdin);
n=0,l=0;
while(scanf("%d%d",&sec[n].x,&sec[n].y)!=EOF)
{
if(sec[n].x>sec[n].y) t=sec[n].x,sec[n].x=sec[n].y,sec[n].y=t;
sec[n].l=sec[n].y-sec[n].x+1;
n++;
}
qsort(sec,n,sizeof(Sec),cmp);
for(i=0;i<n;i++)
{
if(sec[i].x == -1) continue;
for(j=i+1;j<n;j++)
{
if(sec[j].x > sec[i].y) break; //肯定不會(huì)重疊
if(sec[j].x == -1 || sec[j].y>sec[i].y) continue;
if(sec[j].l>l) l=sec[j].l;//sec[i]完全包括sec[j]
sec[j].x = -1; //已經(jīng)考慮過
}
}
for(i=0;i<n;i++)
{
if(sec[i].x == -1) continue;
for(j=i+1;j<n;j++)
{
if(sec[j].x > sec[i].y) break;
if(sec[j].x == -1) continue;
if(sec[i].y - sec[j].x +1 >l) l =sec[i].y-sec[j].x+1;
break;
}
}
cout<<l<<endl;
return 0;
}