I like this. If we can assume that the existing ranges do not overlap, then when sorted they look like:
<--->....<---->.....<---->... etc. Now with a new range, we can use binary search to find where its endpoints would fit in this list. First, the start of the range should be after an even number of elements (otherwise, the new range starts during an existing one). Second, the end of the range should fit in the same space (otherwise, the new range contains at least the start of an existing one). As Aurelian noted, doing this in a vector is problematic when we need to add the new range to the vector, depending on the application (the data validation is logarithmic, but update is linear). This can be solved by using some kind of rank tree, but AFAIK there's no simple way to get this without rolling your own (at least in C++, STL set can't easily be extended to do this). However, for this problem we don't actually need a full rank tree; we only need to check whether the element immediately before the inserted start (if it exists) is not the start of some interval, and that the element immediately before the inserted end is actually the inserted start. I think you can handle both of these by inserting appropriately decorated elements into a vanilla set (actually, probably you'd defer the insertions until the validation is done, but that's just a detail). varun: what you have implemented in your latest reply doesn't look like an interval tree to me; you should look that up (it is more than just overriding "equals" and using a set) On Jan 11, 1:11 am, Matteo Landi <[email protected]> wrote: > What about mapping dates to integer and then use logarithmic search to find > whether surrounding dates ``a'' and ``b'' are a starting and ending point > respectively of a range? > > Cheers, > Matteo > > On Jan/10, Morgan Bauer wrote: > > > > > > > > > > > Map dates to integers and use a range tree. > > > ~mhb > > On Jan 10, 2012 11:31 PM, "varun gupta" <[email protected]> wrote: > > > > Hi, > > > > Lets say user is entering date-range as Start Date and End Date. > > > > Start Date End Date > > > 15/Jan/201212 20/Jan/2012 > > > 25/Jan/201212 28/Jan/2012 > > > 15/Feb/201212 18/Feb/2012 > > > > Assumption: Here start date is always less than equal to end date. > > > > Now if a user enters new start date and end date, I need to validate that > > > newly entered range should not lie in already entered ranges. > > > > for ex: > > > if user enter > > > 20/Jan/2012 - 25/Jan/2012 -> invalid; 20/Jan is already covered in first > > > row. > > > 21/Jan/2012 - 23/Jan/2012 -> valid > > > 16/Feb/2012 - 25/Feb/2012 -> invalid > > > > one way is to linear check already entered rows and compare > > > > new_startDate< startDate and new_endDate> endDate > > > > Any other efficient way? > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Google Code Jam" 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/google-code?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Google Code Jam" 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 > > athttp://groups.google.com/group/google-code?hl=en. > > --http://www.matteolandi.net -- You received this message because you are subscribed to the Google Groups "Google Code Jam" 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/google-code?hl=en.
