区间
题目描述
给定n个闭区间 [ai,bi], i=1,2,…,n. 这些区间的和可以用两两不相交的闭区间的和来表示。你的任务是找到这样的区间数目最少的表示，且把它们按升序的方式写到输出文件中。当且仅当a <= b < c <= d时，区间[a; b] 、[c; d]才是升序
写一个程序完成以下任务：
l 从prz.in中读取区间
l 计算出满足上述条件的两两不相交的区间
l 把找到的区间按升序写入到prz.OUT中
输入
输入文件prz.in的第一行只有一个数n, 3 <= n <= 50000，代表区间数.第I+1行有两个数ai,bi,之间用一个空格隔开，分别表示区间[ai,bi]的起始和结束（1 <= i <= n），1 <= ai <= bi <= 1000000
输出
输出文件prz.out应该包含计算出的所有区间，每行写一个区间，每行只有两个数，分别是区间起始和结束，之间用一个空格分开。记住必须是按升序输出。
样例输入
5
5 6
1 4
10 10
6 9
8 10
样例输出
1 4
5 10
题解：
首先有两种方法：
第一种：用一个快排，以头为第一关键字，尾为第二关键字，排好后直接1~n扫过去。如果接不上就输出。O(n log n+n)
第二种：设一个变量：flag。然后输入时，flag[头]+1,flag[尾]-1，然后头=尾的特判一下。在一个1~1000000过去，每次sum加上flag[i]，若sum变为0，则输出i，若sum由0变大了，就输出i。头=尾的还是要认真处理。
标程：
var
i,j,k,l,n,m,a,b,wh,max:longint;
flag:array[1..1000000]of longint;
bz:array[1..1000000]of boolean;
begin
assign(input,'prz.in');reset(input);
assign(output,'prz.out');rewrite(output);
readln(n);
max:=0;
for i:=1 to n do
begin
read(a,b);
inc(flag[a]);
dec(flag[b]);
if a=b then bz[a]:=true;
end;
wh:=0;
for i:=1 to 1000000 do
begin
if (bz[i]=true)and(wh=0)and(flag[i]=0) then
begin
write(i,' ',i);
writeln;
end
else
begin
if i=159700 then
begin
max:=0;
end;
wh:=wh+flag[i];
if (wh-flag[i]=0)and(flag[i]>0)then
begin
write(i,' ');
end
else
if(flag[i]<0)and(wh=0)then
begin
writeln(i);
end;
end;
end;
close(input);close(output);
end.