算法学习（一）：贪婪算法

/*
 * =====================================================================================
 *
 *       Filename:  GreedSelector.c
 *
 *    Description:  intend to resolve conference schedual problem with Greedy algorithm
 *
 *        Version:  1.0
 *        Created:  09/13/2012 10:01:13 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  scar (gao), [e-mail]
 *        Company:  zecloudd.Inc
 *
 * =====================================================================================
 */

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

void
swap (int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

int
partition (int m[], int n[], int low, int high)
{
    int i = low;
    int j = high;
    int pivot = m[low];

    while (i < j)
    {
        while (i < j && m[j] >= pivot)
            j--;
        if (i < j)
        {
            swap (&m[i], &m[j]);
            swap (&n[i++], &n[j]);
        }
        while (i < j && m[i] <= pivot)
            i++;
        if (i < j)
        {
            swap (&m[i], &m[j]);
            swap (&n[i], &n[j--]);
        }
    }
    return j;
}

void
Quick_sort (int m[], int n[], int low, int high)
{
    int pivot;
    if (low < high)
    {
        pivot = partition (m, n, low, high);
        Quick_sort (m, n, low, pivot - 1);
        Quick_sort (m, n, pivot + 1, high);
    }
}

void
GreedySelector (int n, int B[], int E[], int A[])
{
    int i, j;
    i = 0;
    j = 1;
    A[0] = 1;
    Quick_sort (E, B, 0, n-1);
    printf ("after sort:\n");
    for (i = 0; i < 11; i++)
    {
        printf ("---B=%d,E=%d,A=%d\n", B[i], E[i], A[i]);
    }
    i = 0;
    j = 1;
    while (j < n)
    {
        if (B[j] >= E[i])
        {
            A[j] = 1;
            i = j;
        } else
            A[j] = 0;
        j++;
    }
}

int
main (int argc, char **argv)
{
    int         n = 11;
    int         i;
    int         B[11] = {0};
    int         E[11] = {0};
    int        A[11] = {0};

    for(i = 0; i < 11; i++)
    {
        printf ("B[%d]:",i);
        scanf ("%d  ",&B[i]);
        printf ("E[%d]:",i);
        scanf ("%d  ",&E[i]);
    }
    printf ("before select:\n");
    for (i = 0; i < 11; i++)
    {
        printf ("---B=%d,E=%d,A=%d\n", B[i], E[i], A[i]);
    }
    GreedySelector (n, B, E, A);
    printf ("after select:\n");
    for (i = 0; i < 11; i++)
    {
        printf ("---B=%d,E=%d,A=%d\n", B[i], E[i], A[i]);
    }
    return 0;
}