I implemented following code in java. Is this code look ok in terms of
efficiency and memory ?
class DateRangeTree{
private Date startDate;
private Date endDate;
public DateRangeTree(Date startDate,Date endDate){
this.startDate = startDate;
this.endDate = endDate;
}
@Override
public boolean equals(Object other){
if (this == other) {
return true;
}
if (other instanceof DateRangeTree) {
DateRangeTree newDateRange = (DateRangeTree)other;
if(newDateRange.endDate.before(this.startDate) ||
newDateRange.startDate.after(this.endDate)){
return true;
}
}
return false;
}
I defined a range class and will now create
main method like
public static void main(String[] args) {
Set<DateRangeTree> set = new HashSet<DateRangeTree>();
new Date(Calendar.getInstance().getTimeInMillis());
DateRangeTree range1 =
new test().new DateRangeTree(new
Date(Calendar.getInstance().getTimeInMillis()),
new
Date(Calendar.getInstance().getTimeInMillis()));
DateRangeTree range2 =
new test().new DateRangeTree(new
Date(Calendar.getInstance().getTimeInMillis()),
new
Date(Calendar.getInstance().getTimeInMillis()));
System.out.println(set.add(range1));
System.out.println(set.add(range2));
System.out.println(set.size());
}
------------------------------------------
On Wed, Jan 11, 2012 at 3:38 PM, Aurelian Tutuianu <[email protected]>wrote:
> 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.
>
--
--
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.
