会场安排问题

              由于贪心思想，对结束时间排序即可

①这种冒泡排序会超时

#include<stdio.h>
struct yan{
    int start;
    int end;
    }a[10001],temp;
int main()
{
    int i,j;int s,m;int sum=1;
    scanf("%d",&m);
    while(m--)
    {    int n;
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d %d",&a[i].start,&a[i].end);
        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
             if(a[i].end>a[j].end)
        {
            temp=a[i];
            a[i]=a[j];
            a[j]=temp;
        }   j=0;
        for(i=1;i<n;i++)
        {
            if(a[i].start>a[j].end)
            {
                sum++;
                j=i;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}


、、、、、、、、

②快排确实可以节约大量时间
#include<stdio.h>
struct yan{
    int start;
    int end;
    }a[10001],temp;
    void quicksort(int left,int right)
    {
        int i,j,t,h,temp,temp1;
        if(left>right)
            return;
        temp=a[left].end;
        temp1=a[left].start;
        i=left; j=right;
        while(i!=j)
        {
            while(a[j].end>=temp&&i<j)
                j--;
            while(a[i].end<=temp&&i<j)
                i++;
            if(i<j)
            {
                t=a[i].end;
                a[i].end=a[j].end;
                a[j].end=t;
                h=a[i].start;
                a[i].start=a[j].start;
                a[j].start=h;
            }
        }
        a[left].end=a[i].end;
        a[i].end=temp;
        a[left].start=a[i].start;
        a[i].start=temp1;
        quicksort(left,i-1);
        quicksort(i+1,right);
        return;
    }
int main()
{
    int i,j;int m;
    scanf("%d",&m);
    while(m--)
    {    int n;int sum=1;
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d %d",&a[i].start,&a[i].end);
         quicksort(0,n-1);


        j=0;
        for(i=1;i<n;i++)
        {
            if(a[i].start>a[j].end)
            {
                sum++;
                j=i;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

、、、、、、、、

大神迷之操作
#include<stdio.h>
#include <vector>
#include<algorithm>
#include<math.h>
using namespace std;
struct activ
{
int begin;
int end;
};
bool cmp( activ a,activ b)
{
return a.end<b.end;
}
int main()
{
//freopen("1.txt","r",stdin);
int n;
scanf("%d",&n);
while (n--)
{
int m;
scanf("%d",&m);
vector<activ> vec;
for(int i=0;i<m;i++)
{
activ a;
scanf("%d%d",&a.begin,&a.end);
vec.push_back(a);
}
 
sort(vec.begin(),vec.end(),cmp);  
int count=vec.size();
int k=0;
for (int i=1;i<vec.size();i++)
{
if(vec[i].begin <= vec[k].end)
count--;
else k=i;
}
printf("%d\n",count);
}
 
return 0;
}