c语言贪心算法求活动安排

1.问题描述

描述
给定个活动，每个活动安排的时间为。求最多可以选择多少个活动，满足选择的活动时间两两之间没有重合。
输入描述：
第一行输入一个整数，表示可选活动个数。
接下来的行，每行输入两个整数 。，表示第i个活动的时间。
输出描述：
输出一行一个整数，表示最多可选择的活动数。

2.源码实现

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

typedef struct range {
    char delete;
    int start;
    int end;
} range;

static int part(range *a, int low, int high)
{
    range pivot = a[low];
    int t;

    printf("low=%d, high=%d\n", low, high);

    while(low < high)
    {
        while(low < high && a[high].start >= pivot.start)
        {
            high--;
        }

        a[low] = a[high];

        while(low < high && a[low].start <= pivot.start)
        {
            low++;
        }

        a[high] = a[low];
    }

    a[low] = pivot;

    return low;
}

void quick_sort(range *a, int low, int high)
{
    if(low < high)
    {
        int pivot = part(a, low, high);

        quick_sort(a, low, pivot-1);
        quick_sort(a, pivot+1, high);
    }
}

int shell_sort(range *s, int n)
{
    range tmp;
    int gap;
    int i;
    int j;

    for(gap=n/2; gap>0; gap/=2)
    {
        for(i=gap; i<n; i++)
        {
            tmp = s[i];

            for(j=i; j>=gap && tmp.start < s[j-gap].start; j-=gap)
            {
                s[j] = s[j-gap];
            }

            s[j] = tmp;
        }
    }

    return 0;
}


void print_vec(range *a, int n)
{
    int i;

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

int solve(range *r, int n)
{
    int u = n;
    int i = 0;

    shell_sort(r, n);

    while(i < n-1)
    {
        if(r[i].end > r[i+1].start)
        {
            if(r[i].end <= r[i+1].end)
            {
                r[i+1] = r[i];
            }

            r[i].delete = 1;
            u--;
        }

        i++;
    }

    return u;
}

int main()
{
    range r[2*100000];
    int i;
    int n;
    int u;

    scanf("%d", &n);

    if(n < 1 || n > 2*100000)
    {
        return -1;
    }

    for(i=0; i<n; i++)
    {
        scanf("%d %d", &(r[i].start), &(r[i].end));

        r[i].delete = 0;
    }

    u = solve(r, n);

    printf("%d\n", u);

    return 0;
}

3.编译源码

$ gcc -o test test.c -std=c89

4.运行及其结果

$ ./test
3
1 4
1 3
3 5
2