meeting schedule

my code :

 

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

void seperate( int *a, int *beg, int *fin, int length );

void quick_sort( int *beg, int *fin, int left, int right );

int partition( int * beg, int *fin, int left, int right );

void swap( int *beg, int *fin, int idx1, int idx2  );

int meeting_schedule( int *beg, int *fin, int len );

int main( void )
{
    int run;
    int number;
    int i = 0;
    int right;
    scanf(“%d”, &run);

    while( run– )
    {
        scanf(“%d”, &number);
        int *a = ( int *)malloc(sizeof(int) * number * 2);
        i = 0;
        while( i < number * 2)
        {
            scanf( “%d”, &a[i] );
            i++;
        }

        int *beg = ( int *)malloc(sizeof(int) * number);
        int *fin = ( int *)malloc(sizeof(int) * number);

        seperate( a, beg, fin, number * 2 );

        right = number – 1 ;

        quick_sort( beg, fin, 0, right );

        printf(“%d\n”, meeting_schedule( beg, fin, number ));

        free( a );
        free( beg );
        free( fin );

    }
    return 0;
}

// array beg and fin have been sorted already
int meeting_schedule( int *beg, int *fin, int len )
{
    int counter = 0;
    int i;
    int end = fin[0];
    int start ;

    if( fin[0] > beg[0] )
    {
        counter = 1;
    }
    for( i = 1; i < len; i++ )
    {
        if( beg[i] > end )
        {
            start = beg[i];
            end = fin[i];
            counter++;
        }
    }
    return counter;
}

void seperate( int *a, int *beg, int *fin, int length )
{
    int i;
    int j = 0;
    for( i = 0; i < length-1; i+=2 )
    {
        beg[j] = a[i];
        fin[j] = a[i+1];
        j++;
    }
}

void quick_sort( int *beg, int *fin, int left, int right )
{
    if( right – left <= 0 )
    {
        return;
    }
    else
    {
        int par = partition( beg, fin, left, right );
        quick_sort( beg, fin, left, par – 1);
        quick_sort( beg, fin, par + 1, right );
    }
}

int partition( int *beg, int *fin, int left, int right )
{
    int pivot = fin[right];
    //int leftPtr = left – 1;
    //int rightPtr = right + 1;

    int leftPtr = left;
    int rightPtr = right;

    while( 1 )
    {
        //while( leftPtr < right && fin[++leftPtr] < pivot );
        //while( rightPtr > left && fin[–rightPtr] > pivot );
        for( ; fin[leftPtr] < pivot && leftPtr < right; leftPtr++ );
        for(; fin[rightPtr] > pivot && rightPtr > left; rightPtr– );

        if( leftPtr >= rightPtr )
        {
            break;
        }
        else
        {
            swap( beg, fin, leftPtr, rightPtr );
        }
    }

    return leftPtr;
}

void swap( int *beg, int *fin, int idx1, int idx2  )
{
    int temp1 = fin[idx1];
    int temp2 = beg[idx1];

    fin[idx1] = fin[idx2];
    fin[idx2] = temp1;

    beg[idx1] = beg[idx2];
    beg[idx2] = temp2;
}

Advertisements
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s