5th qs r = R(3-2sqrt(2))
On Aug 25, 1:56 pm, vikas <[email protected]> wrote: > @ All, > 1. build a interval tree using startpoints as the key > 2. augment this tree such that each interval contains the number of > ppl arrived, in this case 1. > 3. use this tree and traverse , use this check, if start/end of tree > node is inbetween the interval you are searching, person was there. > > sample code > getMaxNumPpl(node *root, int start, int end) > { > int n = 0; > if(root == NULL) return 0; > if(CHECK(root->start, root->end, start, end)){ > n++; > } > n += getMaxNumPpl(root->left, start, end); > n += getMaxNumPpl(root->right, start, end); > return n; > > } > > On Aug 24, 8:42 pm, rakesh kumar <[email protected]> wrote: > > > > > > > > > Hi > > > Anybody has answer for sphere problem...could you please proivde > > > On Wed, Aug 24, 2011 at 9:10 PM, rakesh kumar > > <[email protected]>wrote: > > > > 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 <[email protected]> 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 [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]. > > >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
