Thanks indeed to all who helped. I think the best response i get is from Nat Padmanabhan, Interval Tree seems a sound approach.
Regards, Asif On Sun, Apr 26, 2009 at 7:34 PM, Nat Padmanabhan <[email protected]>wrote: > http://en.wikipedia.org/wiki/Interval_tree > > > On Thu, Apr 23, 2009 at 4:53 AM, Asif <[email protected]> wrote: > >> >> Hi, >> >> I recently have been asked following algorithm question. >> >> >> An employee has > 500 time cards on each day. These cards could have >> erranous time card data like cards can be overlapped. There is a >> solution present >> for this problem but that runs in O(n2). We need to devise an >> algorithm that should have time complexity in O(Xn). >> >> >> Sample Time card data could be >> >> >> In | Out // >> 08:00 | 10:00 //Overallping with below time card >> 09:00 | 11:00 //Overallping with above time card >> 14:00 | 16:00 //Not overlapping >> 16:00 | 17:00 //Not overlapping >> >> >> Is there an efficient algorithm to do this in O(n + n, ...) >> >> Asif >> >> >> > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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 -~----------~----~----~----~------~----~------~--~---
