I don't know if the complexities of sorting are also considered in the calculation of total cost in this algorithm. Can you please help me identify, if it's taken into account.
-- Thanks & Regards, Varun Narang. 2 is not equal to 3, not even for large values of 2. - Grabel's Law 2009/4/26 Rasifiel <[email protected]> > > There is efficient algo for O(nlogn+m) where m - is count of > intersections: > Make queue and put there events of starting and ending of time slots. > After make 2nd priority queue. > Sort them. > After that iterate on 1st queue: (N) > If you get start event - > Iterate over second queue and add info about intersections of elements > of 2nd queue and current element of 1st queue. (summary for all > iterations - M) > Add card number to 2nd queue (log N) > If you get end event - > Delete card number from 2nd queue (log N) > > Sorry for bad english) > > On 23 апр, 14:53, 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 -~----------~----~----~----~------~----~------~--~---
