Hi All, for checkouts problem how about finding the median for all the times....
8-00 8-15 830 sort the second list 8-30 900 920 if we take the mediun of whole list then it will be 8-30 where max no of people will be present Will it work.. Any body has any idea?? On Wed, Aug 24, 2011 at 12:58 AM, DK <divyekap...@gmail.com> wrote: > Well, strictly speaking, you don't need any complex data structures: > > *1. Create an array of entities* > eg. Person data[100]; > where > struct Person { > .... // Person data > }; > > *2. Create an array of timestamps:* > Event time[200]; // Note: double the size of the Person data array. One for > start and one for finish time. > where > struct Event { > Person *p; // To maintain a reference to the original person data > int time; // say in seconds > bool finish; // default: false > }; > > *3. Sort the time array based on the time value* > > *4. Now, simply maintain a counter* > int num_people = 0; > int max = 0; > for each event in time: > if(event.finish == true) --num_people; > else ++num_people; > if(num_people > max) max = num_people; > > Time Complexity: O(N log N) > Space Complexity: O(N) > > -- > DK > > http://twitter.com/divyekapoor > http://www.divye.in > http://gplus.to/divyekapoor > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/XrR_OjPOVagJ. > > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.