I would choose interval tree also. When you want to query if a new interval in in another interval, simply query for both ends of the interval and do interval intersection. If intersection is not null than is included in those intervals. I really don't see how can be used range trees for that. But could be possible. Storing a sorted array is not an option because after you do the validation you should insert those points in the vector and that takes linear time.
On Wed, Jan 11, 2012 at 11:42 AM, Vikram Gaur <[email protected]> wrote: > i think mapping dates to integers and using interval trees to check the > intersection can be done :) > > Regards, > Vikram > > On Wed, Jan 11, 2012 at 1:41 PM, 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 at >> http://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. >> >> > > > -- > Thanks and Regards > Vikram Gaur > Software Engineer > Samsung Engineering Labs, Noida > +91-9818540102 > > "Since human beings themselves are not fully debugged yet, there will be > bugs in your code no matter what you do." - Chris Mason > > -- > 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 at http://groups.google.com/group/google-code?hl=en.
