Monish, please take a look at a similar problem about poor elephants in the neighboring topic started today. I believe the problem has a similar solution. Each start point increases the no. of active intervals by one; each end point decreases it. So, we do the following:
1. Convert the input array of pairs (BTW, the points don't have to be of an integral type!) into the following vector: { {2,+1}, {3,-1}, {3, +1}, {4, -1}...} This takes O(N) time and O(N) additional memory 2. Sort the vector by: a) ascending .first; b) descending .second -- this makes sure we count the intervals properly in case multiple intervals start and end at the same point. Complexity is O(N*logN). 3. Convert "relative" counters to "absolute"; complexity is O(N). int count = 0; for (int i = 0; i < v.size(); ++i) { count += v.second; assert (count >=0); v.second = count; } assert (count == 0); 4. After this preparation work ( O(N*logN) time, O(N) memory), answering the question about the number of intervals for any numbers takes O(logN) -- use lower_bound() to binary search in the sorted vector. On Sunday, June 9, 2013 3:20:46 AM UTC-4, Monish Gupta wrote: > > There are n Intervals. Given a set of m numbers, tell in how many > intervals does each number exists. > Example: 4 Intervals: [2,3] [3,4] [1,4] [3,10]. Numbers {2,4,11} > For 2 -> 1 as 2 lies only in 1 interval [2,3] > For 4 -> 3 as 4 lies in 3 intervals > For 11 -> 0 as 11 lies in none of the given 4 intervals. > > It can be easily done in O(m*n) by traversing n intervals for each number > in the given set of m numbers. How would improve this? > > Note: I could not fully recall, but I have seen very similar question in > codechef but could not find the same. > -- 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.