Friday, 2 May 2014

Maximum disjoint events

There are n events given with their starting and ending times. Find the maximum number of disjoint events that a person can attend.

Motivation:. There are a number of movies playing in a cinema hall.  Further, the screening time of a movie may overlap with the screening time of another movie. Since a person can physically be present in only one movie at a time, what is the maximum number of movies that can be watched by a person in one day.

Input : First line contains integer n denoting the number of events.
Second line contains starting time of n events separated by spaces
Third line contains finishing time of n events separated by spaces

Output: Maximum number of events that a person can attend.
Explanation: A person can attend event 1 from time 1 to 4, he cannot attend event 2 because this event starts before the first event ends however he can attend the third event after completing 1st event. 
1-4 -> 5-9 
hence he can attend maximum of 2 events.

Constraints:  
1<=n<=10, here n is the number of events
1<=s<=1000, this is the range of the starting times
1<=f<=1000, this is the range of the finishing times






#include<stdio.h>
#include<stdlib.h>
struct Event
{
   int start_time,finish_time;    
};
int comp (const void * elem1, const void * elem2)
{
struct Event  f = *((struct Event*)elem1);
struct Event  s = *((struct Event*)elem2);
if (f.finish_time > s.finish_time) return  1;
if (f.finish_time < s.finish_time) return -1;
return 0;
}
int printMaxActivities(struct Event events[], int n)
{
  int count=0,temp=0,i,j;
  struct Event x;
  for(i = 0; i < n; i++)   
  {
   for(j = i + 1; j < n; j++)  
   {  
     if((events[i].start_time)>(events[j].start_time))
      {  
       x=events[j];  
       events[j]=events[i];
       events[i]=x;
      }
   }
  }
  for(i=0;i<n;i++)
  {
   temp=1;
 x=events[i];
 for(j=0;j<n;j++)
   {
    if(x.finish_time <= events[j].start_time)
        {
         ++temp;
         x.finish_time=events[j].finish_time;
        }
   }
   if(count<temp)
   count=temp; 
  }
  return count;
}
int main()
{
   int n,count,i;
   scanf("%d",&n);
   struct Event *events = (struct Event *)malloc(n*sizeof(struct Event));
   for(i=0;i<n;i++)
       scanf("%d",&events[i].start_time);
   for(i=0;i<n;i++)
       scanf("%d",&events[i].finish_time);
   count = printMaxActivities(events,n);
   printf("%d",count);
    return 0;
}

No comments: