/* This program finds a conflict-free, optimal schedule
   of activities. More precisely, given the start
   and finish times of a set of activities, the program
   finds a subset of activities of maximum size in which,
   given any two distinct activities, one always finishes
   before the other starts.

   This file must be linked to the file sort_str.c
   that contains the string-sorting function sort_str.

   The input is of the form

   sssssfffff
   sssssfffff
     ...

   where each line gives the start and finish times of one
   activity. sssss is the start time (an integer) right-justified
   in the columns 1-5, and fffff is the finish time (also an
   integer) right-justified in columns 6-10. The input file name
   is supplied on the command line.
 */         

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

#define Max_No_Strings 100
#define Str_Len 12

const int Field_Width = 5;

/* select[ i ] = 0, if activity i is not selected.
   select[ i ] = 1, if activity i is selected. */
int select[ Max_No_Strings ];

/* count = number of activities */
int count;

char str[ Max_No_Strings ][ Str_Len ];

void sort_str( void *s, int numb_elts,
               int str_size, int start, int length ),
     greedy_selector( void );

main( int argc, char **argv)
{
   int i;
   FILE *fp;

   fp = fopen( argv[ 1 ], "r" );

   for ( count = 0;
         count < Max_No_Strings &&
            fgets( str[ count ], Str_Len, fp ) != NULL;
         count++ )
      ;

   greedy_selector();

   printf( "\n\nOptimal schedule:\n\n" );

   for ( i = 0; i < count; i++ )
      if ( select[ i ] )
         printf( "%s", str[ i ] );

   return EXIT_SUCCESS;
}

/* This function implements the greedy
   algorithm to find an optimal schedule. */
void greedy_selector( void )
{
   int i, j;

   /* Sort strings by finish time.
      The arguments to sort_str are:

         array of strings
         number of strings
         size in bytes of each string (all strings must
            be the same length)
         index of substring on which to sort
         length of substring on which to sort

      We are sorting on finish times which occur in columns
      6-10: begin at index Field_Width and of length
      Field_Width.
    */
   sort_str( str, count, sizeof ( str[ 0 ] ),
             Field_Width, Field_Width );

   /* always select activity with smallest finish time */
   select[ 0 ] = 1;

   for ( j = 0, i = 1; i < count; i++ )
      /* if start time of next activity (i) in list is
         >= finish time of last activity (j) picked,
         pick activity i */
      if ( strncmp( str[ i ], str[ j ] + Field_Width,
                    Field_Width ) >= 0 ) {
         select[ i ] = 1;
         j = i;
      }
}