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.
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 times1<=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:
Post a Comment