Re: [algogeeks] Re: Max-Overlapping Intervals
it is better to use Binary Index Tree ( Fenwick Tree) with time complexity O(log n) to update and O(n * log n) for finding max overlapping interval . http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=binaryIndexedTrees this link can be useful for understanding how it will work. Regards, Ritesh Kumar Mishra Information Technology Third Year Undergraduate MNNIT Allahabad On Mon, Feb 25, 2013 at 10:46 AM, Sairam ravu...@gmail.com wrote: First sort the intervals So, in our example it will be as follows (2,7),(5,10),(6,15). make a map which has got interval with corresponding number of overlaps Now, iterate through each of the interval for(i=0;i(n-1);i++) for(j=0;jn;j++) update the map with the number of overlaps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
Colleagues, how about the following?
At each start point, the total number of leaving elephants increases by
one; at each end point, it decreases by one. We:
1. form a vector of pairs: {5, +1}, {10, -1}, {6, +1}, {15, -1}, {2, +1},
{7, -1} ... -- this takes O(N) time and O(N) additional space
2. Sort this vector by a) ascending .first; b) descending .second (so that
if at the same time there are both newborn and just dead elephants, we
count the overall number properly) -- O(N* logN)
3. Scan the sorted vector keeping maximal value of the counter -- O(N)
int maxcount = 0, count = 0, index = 0;
for (i = 0; i v.size(); ++i) {
count += v[i].second;
if (count maxcount) {
maxcount = count; index = i;
}
}
4. print 'maxcount' between v[index] and v[index+1]
On Thursday, February 21, 2013 4:40:17 AM UTC-5, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
igor way is the optimized way using prefix sum just a small correction with
in life period of (l,r) you have to do v[l]++, v[r+1]--(v is initialized
to zero ) take a prefix sum of v and return the max value containing index
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
ohh..sorry you have to return interval so give the starting index of prefix
sum array to the last index of containing the maximum value of array
On Thursday, February 21, 2013 3:10:17 PM UTC+5:30, NITHIN HOTKER wrote:
Given life time of different elephants find *period when maximum number
of elephants lived.*
Eg [5, 10], [6, 15], [2, 7] etc. year in which max no elephants exists.
When this is put on paper the answer is [6,7] .
Is it* [Max(start interval),Min(end interval)] * such that start end
interval ?? I've checked this for 2-3 cases and it works .
Given another interval , find set of intervals in which given point lies .
This could be done using augumented data-structure using Tree .
Let's create a balanced BST using the asc order {2,5,6,7,10,15}
What after this ???
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Max-Overlapping Intervals
First sort the intervals So, in our example it will be as follows (2,7),(5,10),(6,15). make a map which has got interval with corresponding number of overlaps Now, iterate through each of the interval for(i=0;i(n-1);i++) for(j=0;jn;j++) update the map with the number of overlaps. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
