题解 | #活动安排#

#include <stdio.h>
#include<stdlib.h>

typedef struct time
{
    int x,y;
}time;
time arr[200000];//定义结构体数组，关联活动的开始和结束时间

void merge(time *arr,int l,int m,int r)//归并排序，防止时间超限
{
    int templ=l,tempr=m+1,temp=0;
    time *brr=(time *)malloc((r-l+1)*sizeof(time));
    while(templ<=m&&tempr<=r)//将活动结束的时间按从小到大排列
    {
        if(arr[templ].y<arr[tempr].y)
        {
            brr[temp++]=arr[templ++];
        }
        else
        {
            brr[temp++]=arr[tempr++];
        }
    }
    while(templ<=m)
    {
        brr[temp++]=arr[templ++];
    }
    while(tempr<=r)
    {
        brr[temp++]=arr[tempr++];
    }
    for(int i=0;i<r-l+1;i++)
    {
        arr[l+i]=brr[i];
    }
    free(brr);
}

//分解
void msort(time *arr,int l,int r)
{
    int m=(l+r)/2;
    if(l<r)
    {
        msort(arr,l,m);
        msort(arr,m+1,r);
        merge(arr,l,m,r);
    }
}


int main() 
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&arr[i].x,&arr[i].y);
    }
    msort(arr,0,n-1);
    int sum=1;
    for(int i=0;i<n-1;)
    {
        int temp=arr[i].y;
        while(1)
        {
            if(arr[i+1].x>=temp) //取后一个活动开始时间慢于当前活动的结束时间
            {
                sum++;
                break;
            }
            else if(i<n-2) i++;
            else break;//防止无限循环
        }
        i++;
    }
    printf("%d\n",sum);
    return 0;
}