非洲小孩

快速排序+贪心算法：
--------------------------------------------------------------------------------
#include<stdio.h>
struct Node  // 定义结构体，方便处理数据
{
    int start;  //定义开始时间
    int end;    //定义结束时间
}a[200];

void quick_sort(struct Node *arr, int l, int r)  //对结束时间进行排序
{
    if (l < r)     //进行判断，用来终止递归
    {
        int i = l, j = r, x = arr[l].end;
        struct Node temp = arr[l];          //用来交换结构体数组变量
        while (i < j)
        {
            while (i < j && x <= arr[j].end)    //从右往左找一个小于x的数
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && x > arr[i].end)     //从左往右找一个大于x的数
                i++;
            if (i < j)
                arr[j--]= arr[i];
        }
        arr[i] = temp;
        quick_sort(arr, l ,i - 1);              //递归调用，分治思想，左边分治。
        quick_sort(arr, i + 1, r);              //右边分治
    }
}

int main()
{
    int n;
    while (scanf("%d",&n) != EOF)
    {
        int i, j, a1, a2, b1, b2, temp, sum = 1;
        for (i = 0; i < n; i++)
        {
            scanf("%d:%d-%d:%d", &a1, &a2, &b1, &b2);
            a2 = a1 * 60 + a2;
            b2 = b1 * 60 + b2;
            if (a2 > b2)        // 判断前面的时间是否小于后面的时间
            {
                temp = a2;
                a2 = b2;
                b2 = temp;
            }
            a[i].start = a2;
            a[i].end = b2;
        }
        quick_sort(a, 0, n-1);  // 注意是从n-1开始
        j = 0;
        for (i = 0; i < n; i++)
        {
            if (a[i].start > a[j].end)  //当下一个的开始时间大于现在的结束时间时，说明需要开关一次水龙头。
            {
                j = i;
                sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}
--------------------------------------------------------------------------------




冒泡排序+贪心算法：
--------------------------------------------------------------------------------
#include<stdio.h>
struct Node
{
    int start;
    int end;
}a[100];

void sort(struct Node *arr, int n)
{
    struct Node temp;
    int i, j;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - i - 1; j++)
        {
            if (arr[j].end > arr[j+1].end)
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main()
{
    int n,i,j;
    while(scanf("%d",&n)!=EOF)
    {
        int a1,a2,b1,b2,temp,sum=1;
        for(i=0;i<n;i++)
        {
            scanf("%d:%d-%d:%d",&a1,&a2,&b1,&b2);
            a2+=a1*60;b2+=b1*60;
            if(a2 > b2)
            {
                temp=a2;
                a2=b2;
                b2=temp;
            }
            a[i].start=a2;
            a[i].end=b2;
        }
        sort(a,n);
        for(i=0,j=0;i<n;i++)
        {
            if(a[i].start > a[j].end)
            {
                j=i;
                sum++;
            }
        }
        printf("%d\n",sum);
    }
}
--------------------------------------------------------------------------------