求2组.最大化节目数量..
**贪心策略:**
....按照结束时间排序.
....若节目可以放.则必定放.
....尽量放在结束时间长的1组.
**证明:**
....对于其中1组.设它结束时间为$p$.
....若有$p <= a_i$.则该节目可以放在这组上.
....我们希望结束时间越小越好.用来放置更多的节目.
....那么取$p = min(b_i), (p <= a_i, 1 <= i <= n)$.
....若有$b_j$同样满足$(p <= a_j, 1 <= j <= n)$.
....用$b_j$代替$b_i$.
....那么节目总个数不会变.
....因$b_i <= b_j$.$p$可能增大.并非最优.
....所以按结束时间排序的思想正确.
....从2组的角度来看.
....若要使节目数+1.
....$p_1$与$p_2$必然存在1个$p = min(b_i)$.
....所以若$p_1 < p_2$.且$p_2 <= a_i, (1 <= i <= n)$.
....放在$p_1$则留下$p_2, b_i$.
....放在$p_2$则留下$p_1, b_i$.
....因为$p_1 < p_2$.
....放在$p_2$更优.
完毕.
~~还是很假.~~
Diu代码.
```cpp
program P2255;
var
a,b:array[0..151] of longint;
i,j,n,t,t1,s:longint;
begin
readln(n);
for i:=1 to n do
readln(a[i],b[i]); //开始与结束时间....
for i:=1 to n-1 do //按结束时间排序....
for j:=i+1 to n do
if (b[i]>b[j]) or (b[i]=b[j]) and (a[i]>a[j]) then
begin
t:=b[i];
b[i]:=b[j];
b[j]:=t;
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
t:=0;
t1:=0; //2组分别的结束时间.
s:=0; //具体节目数量..
for i:=1 to n do
if a[i]>=t then //能放在第1组..
begin
inc(s);
if (t1>=t) and (a[i]>=t1) then t1:=b[i] //第2组能放.且更优..
else t:=b[i];
end
else if a[i]>=t1 then //能放在第2组..
begin
inc(s);
t1:=b[i];
end;
writeln(s);
end.
```
(ಡωಡ).