Account Options

  1. Sign in
The old Google Groups will be going away soon.
Switch to the new Google Groups.
Google Groups Home
« Groups Home
Google Code Jam
Home
+ new post
About this group
Join this group
Efficient algorithm to compare date range
Options
There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic.
There was an error processing your request. Please try again.
flag
   7 messages - Collapse all  -  Translate all to Translated (View all originals)
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
varun gupta  
View profile  
 More options Jan 10, 11:31 pm
From: varun gupta <varun.gt...@gmail.com>
Date: Wed, 11 Jan 2012 10:01:05 +0530
Local: Tues, Jan 10 2012 11:31 pm
Subject: Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author

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 must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Morgan Bauer  
View profile   Translate to Translated (View Original)
 More options Jan 10, 11:32 pm
From: Morgan Bauer <bauer.mor...@gmail.com>
Date: Tue, 10 Jan 2012 23:32:59 -0500
Local: Tues, Jan 10 2012 11:32 pm
Subject: Re: [gcj] Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author

Map dates to integers and use a range tree.

~mhb
On Jan 10, 2012 11:31 PM, "varun gupta" <varun.gt...@gmail.com> wrote:


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Matteo Landi  
View profile   Translate to Translated (View Original)
 More options Jan 11, 3:11 am
From: Matteo Landi <mat...@matteolandi.net>
Date: Wed, 11 Jan 2012 09:11:16 +0100
Local: Wed, Jan 11 2012 3:11 am
Subject: Re: [gcj] Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author
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:

--
http://www.matteolandi.net

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Vikram Gaur  
View profile   Translate to Translated (View Original)
 More options Jan 11, 4:42 am
From: Vikram Gaur <1989.vik...@gmail.com>
Date: Wed, 11 Jan 2012 15:12:13 +0530
Local: Wed, Jan 11 2012 4:42 am
Subject: Re: [gcj] Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author

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 <mat...@matteolandi.net>wrote:

--
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 must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Aurelian Tutuianu  
View profile  
 More options Jan 11, 5:08 am
From: Aurelian Tutuianu <padre...@gmail.com>
Date: Wed, 11 Jan 2012 12:08:41 +0200
Local: Wed, Jan 11 2012 5:08 am
Subject: Re: [gcj] Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author

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.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
varun gupta  
View profile  
 More options Jan 19, 4:16 am
From: varun gupta <varun.gt...@gmail.com>
Date: Thu, 19 Jan 2012 14:46:50 +0530
Local: Thurs, Jan 19 2012 4:16 am
Subject: Re: [gcj] Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author

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 <padre...@gmail.com>wrote:

--

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
sumuduf@gmail.com  
View profile  
 More options Jan 19, 6:38 am
From: "sumu...@gmail.com" <sumu...@gmail.com>
Date: Thu, 19 Jan 2012 03:38:49 -0800 (PST)
Local: Thurs, Jan 19 2012 6:38 am
Subject: Re: Efficient algorithm to compare date range
Print | Individual message | Show original | Report this message | Find messages by this author
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 <mat...@matteolandi.net> wrote:


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
End of messages
« Back to Discussions « Newer topic     Older topic »

Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2012 Google