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.
