Tuesday, June 3, 2014

Find the conflicting appointments

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

/* 
   Time interval format: yyymmddhhmm yyyymmddhhmm 

   Example Input:
   --------------
   4
   5 6
   1 9
   7 8
   2 10

   Process:
   --------

   Data Structure
   time_node to store the intervals
    ------------------------------
   | timestamp | is_start | index |
    ------------------------------

   Step 1:
   -------

   - stores the timestamps into an array
   
    -----------   -----------   -----------   -----------
   | 5 | 1 | 0 | | 6 | 0 | 0 | | 1 | 1 | 1 | | 9 | 0 | 1 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 2 | 1 | 3 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7

   Step 2:
   -------

   - Sort the array wrt the timestamp value

    -----------   -----------   -----------   -----------
   | 1 | 1 | 1 | | 2 | 1 | 3 | | 5 | 1 | 0 | | 6 | 0 | 0 |
    -----------   -----------   -----------   -----------
         0             1             2             3

    -----------   -----------   -----------   ------------
   | 7 | 1 | 2 | | 8 | 0 | 2 | | 9 | 0 | 1 | | 10 | 0 | 3 |
    -----------   -----------   -----------   ------------
         4             5             6              7
   
   Step 3:
   -------

     3.1 Push the index value to the index_list if it is the start of an interval
     3.2 Delete the index value from the index_list if it is the end of an interval
       3.2.1 add all the index values from the index_list to the conflict_list of the this interval
       3.2.2 add this interval index into the conflict_list of all the index values in the index_list
*/


/* Index to find parent and the childern */
#define LEFT(a) (2*(a+1) -1)
#define RIGHT(a) (2*(a+1))
#define PARENT(a) ((a-1)/2)

typedef enum boolean {
  FALSE = 0,
  TRUE = 1
} bool;

/* To store the calendar appointment intervals */
typedef struct time_node time_node;
struct time_node {
  unsigned long long timestamp;
  bool is_start;
  int index;
};

/* To store the conflicts */
typedef struct index_node index_node;
struct index_node {
  int index;
  index_node *next;
};

/* Swap function */
#define XORSWAP(a, b) ((a.timestamp)^=(b.timestamp),(b.timestamp)^=(a.timestamp),(a.timestamp)^=(b.timestamp), \
                         (a.is_start)^=(b.is_start),(b.is_start)^=(a.is_start),(a.is_start)^=(b.is_start), \
                         (a.index)^=(b.index),(b.index)^=(a.index),(a.index)^=(b.index))

/* Heapify */
void maxheapify (time_node *list, int count, int index)
{
  int left = LEFT (index);
  int right = RIGHT (index);
  
  int largest = index;
  
  if (left <= count-1 && list[left].timestamp > list[largest].timestamp)
    largest = left;
  if (right <= count-1 && list[right].timestamp > list[largest].timestamp)
    largest = right;
  
  if (largest != index)
  {
    XORSWAP (list[index], list[largest]);
    maxheapify (list, count, largest);
  }
}

/* Buids the heap */
void build_max_heap (time_node *list, int count)
{
  for (int i = (count-1)/2; i >= 0; i--)
  {
    maxheapify (list, count, i);
  }  
}

/* Sorts the intervals using heap sort */
void heap_sort (time_node *list, int count)
{
  build_max_heap (list, count);
  
  int tmp_count = count-1;
  for (int i = count-1; i > 0; i--)
  {
    XORSWAP (list[0], list[i]);
    maxheapify (list, i, 0);
  }
}

/* Adds the index node into the list */
bool add_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    *list = (index_node *) calloc (1, sizeof (index_node));
    if (NULL == *list)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      (*list)->index = index;
      (*list)->next = NULL;
    }
  }
  else
  {
    index_node *t = *list;
    
    while (NULL != t->next)
      t = t->next;

    t->next = (index_node *) calloc (1, sizeof (index_node));
    t = t->next;

    if (NULL == t)
    {
      fprintf (stderr, "Error: memory allocation failure.");
      return FALSE;
    }
    else
    {
      t->index = index;
      t->next = NULL;
    }
  }
  return TRUE;
}

/* Deletes the index node from the list */
void delete_index_node (index_node **list, int index)
{
  if (NULL == *list)
  {
    return;
  }
  else
  {
    index_node *t = *list;
    index_node *lbo = *list;

    while (t->index != index)
    {
      if (t->next->next == NULL)
      {
        lbo = t;
      }
      t = t->next;
    }
    
    if (t == *list)
    {
      *list = (*list)->next;
      free (t);
    }
    else if (NULL == t->next)
    {
      lbo->next = NULL;
      free(t);
    }
    else
    {
      t->index = t->next->index;
      index_node *d = t->next;
      t->next = t->next->next;
      free (d);
    }
  }
}

int main (int argc, char **argv)
{
  time_node *interval_list = NULL;

  /* Reads the input file for the intervals */
  FILE *fp = NULL;
  fp = fopen ("intervals.txt", "r");
  if (NULL == fp)
  {
    fprintf (stderr, "Error: Could not read the file.");
    return -1;
  }

  int count = 0;
  int readcount = 0;
  int tmp_count = 0;
  
  /* Reads the count */
  readcount = fscanf (fp, "%d", &count);
  if (0 >= readcount)
  {
    fprintf (stderr, "Error: Nothing in the file.");
    return -2;
  }
  
  interval_list = (time_node *) calloc (count*2, sizeof (time_node));
  if (NULL == interval_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* Reads the intervals */
  printf ("Input:\n");
  for(tmp_count = 0; tmp_count < count; tmp_count++)
  {
    if (feof(fp))
    {
      break;
    }
    unsigned long long start = 0;
    unsigned long long end = 0;
    readcount = fscanf (fp, "%llu %llu", &start, &end);
    printf ("%5d) : %llu <-> %llu\n", tmp_count+1, start, end);
    interval_list[tmp_count*2].timestamp = start;
    interval_list[tmp_count*2].is_start = TRUE;
    interval_list[tmp_count*2].index = tmp_count;
    interval_list[tmp_count*2+1].timestamp = end;
    interval_list[tmp_count*2+1].is_start = FALSE;
    interval_list[tmp_count*2+1].index = tmp_count;
  }
  printf ("\n");
  fclose(fp);

  /* Sort the timestamp values */
  heap_sort (interval_list, count*2);
  
  index_node *index_list = NULL;
  index_node **conflict_list = NULL;
  conflict_list = (index_node **) calloc (count, sizeof (index_node*));
  if (NULL == conflict_list)
  {
    fprintf (stderr, "Error: Memory allocation failed.");
    return -3;
  }

  /* main loop to find the conflicts */
  for (int i = 0; i < count*2; i++)
  {
    if (interval_list[i].is_start == TRUE)
    {
      if (FALSE == add_index_node (&index_list, interval_list[i].index))
      {
        fprintf (stderr, "Error: Memory allocation failed.");
        return -3;
      }
    }
    else
    {
      delete_index_node (&index_list, interval_list[i].index);

      index_node *t = index_list;
      while (t)
      {
        if (FALSE == add_index_node (&(conflict_list[interval_list[i].index]), t->index) || 
            FALSE == add_index_node (&(conflict_list[t->index]), interval_list[i].index))
        {
          fprintf (stderr, "Error: Memory allocation failed.");
          return -3;
        }
        t = t->next;
      }
    }
  }

  /* Print the result */
  printf ("Conflicts:\n");
  for (int i = 0; i < count; i++)
  {
    printf ("%5d : ", i+1);
    index_node *t = conflict_list[i];
    while (t)
    {
      printf ("%d ", t->index+1);
      t = t->next;
    }
    printf ("\n");
  }
  return 0;
}
We can use self-balanced binary search tree to keep the index_list to get a better time complexity.

No comments :

Post a Comment