滑雪录像{silver题3}
【问题描述】
冬奥会的电视时刻表包含N (1 <= N <= 150)个节目，每个节目都有开始和结束时间。农民约翰有两台录像机，请计算他最多可以录制多少个节目。
【文件输入】
第一行，一个整数N。
接下来N行每行两个整数，表示一个节目的开始和结束时间，范围为0..1,000,000,000。
【文件输出】
一个整数，表示最多可以录制的节目数量。
【输入样例】
6
0 3
6 7
3 10
1 5
2 8
1 9
【输出样例】
4
【样例说明】
第1台录制节目1和3，第2台录制节目2和4。
思路：一开始觉得用两次DP，第一次DP得出最优解，之后将最优解删去，再DP，最后得出的就是答案，但是本题由于两个录像可能会有覆盖，这样两次DP就需要有特判，然后特判很烦，也就没打，只有70分。后来得知本题原来可以贪心，我也是醉了、、、先将结束时间进行排序，然后记录两台录像机当前最后一个的结束时间，如果一个录像只能由一台相机录，那就给它录，如果两台录像机都可以录此录像，那么就选两台录像机中结束时间晚的那个来录它（至于为什么，也不用说了，自己想）。接下来上代码
1 var 2 s,t:array[0..150]of longint; 3 i,n,t1,t2,ans:longint; 4 5 procedure openit; 6 begin 7 assign(input,'recording.in');assign(output,'recording.out'); 8 reset(input);rewrite(output); 9 end; 10 11 procedure closeit; 12 begin 13 close(input);close(output); 14 end; 15 16 procedure qsort(l,r:longint); 17 var i,j,m,temp:longint; 18 begin 19 i:=l;j:=r;m:=t[(l+r) div 2]; 20 repeat 21 while t[i]<m do inc(i); 22 while t[j]>m do dec(j); 23 if not (i>j) then 24 begin 25 temp:=s[i];s[i]:=s[j];s[j]:=temp; 26 temp:=t[i];t[i]:=t[j];t[j]:=temp; 27 inc(i);dec(j); 28 end; 29 until i>j; 30 if l<j then qsort(l,j); 31 if i<r then qsort(i,r); 32 end; 33 34 35 begin 36 openit; 37 readln(n); 38 for i:=1 to n do readln(s[i],t[i]); 39 qsort(1,n); //快排结束时间 40 t1:=0;t2:=0;ans:=0; 41 for i:=1 to n do 42 begin 43 if (s[i]>=t1) and (s[i]>=t2) then 44 begin 45 inc(ans); 46 if t1>t2 then t1:=t[i] 47 else t2:=t[i]; 48 continue; 49 end; 50 if s[i]>=t1 then begin inc(ans);t1:=t[i]; end; 51 if s[i]>=t2 then begin inc(ans);t2:=t[i]; end; 52 end; 53 writeln(ans); 54 closeit; 55 end.