Have two hash tables(separate chaining).. One for every lower bound and another for every upper bound.
Now hash the numbers into both tables based on their bound values. If you want the numbers of interval Iy(yupper->ylower) then from hash tables now you have two linked lists,one for yupper from upper bound hash table and one for ylower from lower bound hash table. These are in sorted order as you said the inputs are provided in sorted order, they are hashed in sorted order. Now you can merge the lists in O(m+n-1) time,this is the merge routine from merge sort. then just traverse through the merged list to find duplicates(these are common to both list so lie between yupper->ylower), this can be done in O(n). So we can complete our task in linear time Cheers!! Shyam --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
