[BZOJ3433]&&[Usaco2014 Jan]Recording the Moolympics

描述 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 个记录器中最多可放多少个区间.

输入格式 InputFormat

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).

输出格式 OutputFormat

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

样例输入 SampleInput

20
0 65706981
860589705 860927876
202227786 647989992
257778303 548269920
861473494 901215922
319994989 730939635
272041417 752906679
864398454 934871472
70119576 313975498
53680537 626436949
688730951 743752493
591718159 905989210
455970887 727058049
244205544 659672922
103714602 165577922
660160316 746763718
489755801 808022666
0 35911063
46588931 674966962
556479119 582188837

样例输出 SampleOutput

11

来源 Source

Silver

BZOJ 3433

代码 Code

按照右端点排序后，开两个变量表示当前记录器的末端点。然后每次尽量更新端点更右边的记录器。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct recorder
{
    int l,r;
    bool operator < (const recorder& temp) const
    {
        return (r!=temp.r)?(r<temp.r):(l<temp.l);
    }
}a[155];
int ans;
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1);
    ans=0;x=y=-1;
    for (i=1;i<=n;i++)
    {
        if (x>y) swap(x,y);
        if (a[i].l<x) continue;
        if (a[i].l>=x && a[i].l<y) x=a[i].r;
        else y=a[i].r;
        ans++;
    }
    printf("%d\n",ans);
    return 0;
}