@ 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 <rockey.rav...@gmail.com> wrote:
> Hi
>
> Anybody has answer for sphere problem...could you please proivde
>
> On Wed, Aug 24, 2011 at 9:10 PM, rakesh kumar <rockey.rav...@gmail.com>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 <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.
