BZOJ3433: [Usaco2014 Jan]Recording the Moolympics

3433: [Usaco2014 Jan]Recording the Moolympics

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 55 Solved: 34
[Submit][Status]

Description

Being a fan of all cold-weather sports (especially those involving cows), Farmer John wants to record as much of the upcoming winter Moolympics as possible. The television schedule for the Moolympics consists of N different programs (1 <= N <= 150), each with a designated starting time and ending time. FJ has a dual-tuner recorder that can record two programs simultaneously. Please help him determine the maximum number of programs he can record in total.

给出n个区间[a,b).有2个记录器.每个记录器中存放的区间不能重叠.

求2个记录器中最多可放多少个区间.

Input

* Line 1: The integer N.

* Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).

Output

* Line 1: The maximum number of programs FJ can record.

Sample Input

6
0 3
6 7
3 10
1 5
2 8
1 9

INPUT DETAILS: The Moolympics broadcast consists of 6 programs. The first runs from time 0 to time 3, and so on.

Sample Output

OUTPUT DETAILS: FJ can record at most 4 programs. For example, he can record programs 1 and 3 back-to-back on the first tuner, and programs 2 and 4 on the second tuner.

HINT

Source

Silver 鸣谢Alegria_提供译文

题解：

随便打了个贪心居然就过了23333，是数据弱还是怎么？

将区间按右端点排序，维护now[0],now[1]分别表示两个记录器最后的位置

新来的线段先往now大的那个记录器放，放不下再到小的那个里，否则会出现大材小用。。。（提示：过不了样例。。。）

不知道对不对？？？挖坑，以后来想。

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000

 #define maxm 500+100

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int now[],n,ans;

 struct rec{int x,y;}a[maxn];

 inline bool cmp(rec a,rec b)

 {

     return a.y<b.y;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     for1(i,n)a[i].x=read(),a[i].y=read();

     sort(a+,a+n+,cmp);

     now[]=now[]=;

     for1(i,n)

      {

          if(a[i].x>=now[])ans++,now[]=a[i].y;

          else if(a[i].x>=now[])ans++,now[]=a[i].y;

          if(now[]>now[])swap(now[],now[]);

      }

     printf("%d\n",ans);

     return ;

 }

秒客网