Luogu | P2255 Recording The Moolympics | 贪心 / 动态规划


Description

Farmer John 热衷于所有寒冷天气的运动(尤其是涉及到牛的运动),他想录下尽可能多的电视节目。 给出 Moolympics 电视时间表,包含 $N$ 个不同的节目,每个具有指定的开始时间和结束时间。Farmer John 有一个双调谐器录音机,可以同时录制两个节目。 请帮助他确定他能录制的节目的最大数量。


Input Format

第一行一个整数 $N$。

接下来 $N$ 行,第 $i$ 行两个整数表示第 $i$ 个节目的开始时间和结束时间。


Output Format

一行,一个正整数,表示 Farmer John 最多可以记录的节目数量。


Input Sample

Sample 01

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


Output Sample

Sample 01

4


Data Range

$N \le 160$。


Solution

​ 可以想到用动态规划,这里主要说一个贪心。

​ 当使用某台录音机录制某个节目时,如果可以录制,则这个录音机录制的上一个节目的结束时间小于等于这个节目的开始时间。那么考虑按照每个节目的结束时间升序排序。每次从两个录音机里选择一个结束时间靠后并且可以录制当前节目的录音机录制(按照结束时间升序排序录制可以尽量保证录制一个节目的子任务后录音机的结束时间最短,选择一个结束时间靠后的录音机是因为结束时间靠前的录音机可以录制后面条件更为苛刻(开始时间更靠前)的节目),使用这个贪心策略即可通过此题。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::sort;

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct pt{
    int L;
    int R;
    friend bool operator < (pt a,pt b){
        return a.R<b.R;
    }
}S[155];

int N;
int l1;
int l2;
int ans;

int main(){
    Read(N);
    rep(i,1,N){
        Read(S[i].L);
        Read(S[i].R);
    }
    sort(S+1,S+1+N);
    rep(i,1,N){
        if(l1<l2){
            if(S[i].L>=l2){
                ans++;
                l2=S[i].R;
            }
            else if(S[i].L>=l1){
                ans++;
                l1=S[i].R;
            }
        }
        else{
            if(S[i].L>=l1){
                ans++;
                l1=S[i].R;
            }
            else if(S[i].L>=l2){
                ans++;
                l2=S[i].R;
            }           
        }
    }
    printf("%d\n",ans);
    return 0;
}