Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 14 of 14
  1. #1
    Regular Coder
    Join Date
    Apr 2005
    Location
    Texas
    Posts
    448
    Thanks
    24
    Thanked 63 Times in 63 Posts

    Determine Whether Two Time Ranges Overlap

    When it occurred to me that I needed to calculate this, I knew it was over my head. (although I did come up with what I thought to be a pretty clever solution involving a very complex series of arrays...) So I decided to google it. The trouble is, the solution was a little over my head too...
    Sooo I hacked away at it for about an hour, and finally it worked, but on closer inspection I had made a typo from the original algorithm. So I thought I would pose the question to you all...

    Is the original algorithm correct, or flawed? is my interpretation correct/flawed, or the same? I'm not really sure what I did here, but after many tests, I think I got the correct solution.

    original post on http://stackoverflow.com/questions/3...ranges-overlap
    Let CondA Mean DateRange A Completely After DateRange B (True if StartA > EndB)

    Let CondB Mean DateRange A Completely Before DateRange B (True if EndA < StartB)

    Then Overlap exists if Neither A Nor B is true ( If one range is neither completely after the other, nor completely before the other, then they must overlap)

    Now deMorgan's law, I think it is, says that

    Not (A Or B) <=> Not A And Not B

    Which means (StartA <= EndB) And (EndA >= StartB)

    NOTE: This includes conditions where the edges overlap exactly. If you wish to exclude that, change the >= operators to >, and <= to <
    And finally the test scenario that I finally got to work:
    Code:
    <input onclick="this.value=''" onkeyup="TEST()" id=inhour1 value=1>
    <input onclick="this.value=''" onkeyup="TEST()" id=inminute1 value=1>
    <br />
    <input onclick="this.value=''" onkeyup="TEST()" id=outhour1 value=2>
    <input onclick="this.value=''" onkeyup="TEST()" id=outminute1 value=1>
    <br />
    <br />
    <input onclick="this.value=''" onkeyup="TEST()" id=inhour2 value=3>
    <input onclick="this.value=''" onkeyup="TEST()" id=inminute2 value=1>
    <br />
    <input onclick="this.value=''" onkeyup="TEST()" id=outhour2 value=4>
    <input onclick="this.value=''" onkeyup="TEST()" id=outminute2 value=1>
    
    <script>
    function ID(e){return document.getElementById(e)}
    
    function TEST(){
    intime1=(parseInt(ID('inhour1').value,10)*60*60)+(parseInt(ID('inminute1').value,10)*60)
    intime2=(parseInt(ID('inhour2').value,10)*60*60)+(parseInt(ID('inminute2').value,10)*60)
    
    outtime1=(parseInt(ID('outhour1').value,10)*60*60)+(parseInt(ID('outminute1').value,10)*60)
    outtime2=(parseInt(ID('outhour2').value,10)*60*60)+(parseInt(ID('outminute2').value,10)*60)
    
    comp=(intime1 <= outtime2)&&(outtime1 <= intime2)
    
    ID('compare').innerHTML=''
    ID('compare').innerHTML+=intime1+'<br />'
    ID('compare').innerHTML+=outtime1+'<br />'
    ID('compare').innerHTML+=intime2+'<br />'
    ID('compare').innerHTML+=outtime2+'<br />'
    ID('compare').innerHTML+=comp+'<br />'
    
    }
    </script>
    <button onclick="TEST()">compare</button>
    <div id="compare"></div>
    Any feedback would help a lot! I fear using an algorithm that I don't fully understand in production code...

  • #2
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    WOW! Way over-complicating it!

    It's really easy.

    There are only SIX possible conditions with two time ranges.

    In the chart below S and E are for time range 1 and s and e are for time range 2. Start and End times, of course.
    Code:
    -----S-----E-----s-----e-----   1 before 2, no overlap
    -----S--s----E------e--------   overlap
    -----S---s---e---E-----------   2 entirely in 1, overlap
    --s---S----E-----e-----------   1 entirely in 2, overlap
    ---s----S---e---E-----------    overlap
    -----s---e---S----E---------    2 before 1, no overlap
    Okay, so what are the ONLY TWO condions where there is NO OVERLAP?

    Trivial:
    Code:
       WHERE e < S
    or
       WHERE E < s
    NOTE: If it is okay for the end of one range to *exactly* match the start of the other range, then just use <= instead of < of course.

    That conclusion of course matches what you found:
    Code:
    ....(True if StartA > EndB) ... (True if EndA < StartB) ...
    I just find it easier to visualize if I write it as
    Code:
    There is NO OVERLAP if  (StartA > EndB OR StartB > EndA)
    And, yes, you *can* apply deMorgan's law to imply
    Code:
    This IS OVERLAP if (StartA <= EndB AND StartB <= EndA)
    But personally, that's harder for me to visualize when applied to my hand little chart.

    So if what you want is the IS OVERLAP condition, I would just say
    Code:
    There IS OVERLAP if  ( ! (StartA > EndB OR StartB > EndA) )
    or even, using JavaScript for OR:
    Code:
    if  (StartA > EndB || StartB > EndA)
    {
        // NO overlap...we aren't interested in this case for this problem 
    } else {
       alert("overlap has occurred!");
    }
    *** ANYWAY ***

    As I see it, your your comparison is wrong. Compare:
    Code:
    This IS OVERLAP if (StartA <= EndB AND StartB <= EndA)
    
    comp=(intime1 <= outtime2)&&(outtime1 <= intime2)
    Looks to me like yours should be
    Code:
    comp=(intime1 <= outtime2)&&(intime2 <= outtime1)
    or
    comp=(outtime2 <= intime1)&&(outtime1 <= intime2)
    Because I can't tell from your names whethe "intime" means "start" or "end".

    Am I wrong??
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • Users who have thanked Old Pedant for this post:

    blaze4218 (10-07-2011)

  • #3
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    Demo, using names that I know what they mean.

    And showing that if you would use *NAMES* instead of IDs for your <form> fields your code can be much simpler.

    And showing there's no need to get seconds. Getting just minutes (that is, multiplying the hours, only, by 60) is sufficient.
    Code:
    <html>
    <head>
    <script>
    function check(form)
    {
        var start1 = form.starthr1.value * 60 + form.startmn1.value * 1;
        var end1   = form.endhr1.value * 60 + form.endmn1.value * 1;
    
        var start2 = form.starthr2.value * 60 + form.startmn2.value * 1;
        var end2   = form.endhr2.value * 60 + form.endmn2.value * 1;
    
        if ( start1 > end1 ) 
        {
            alert("end1 time must be after start1 time");
            return;
        }
        if ( start2 > end2 ) 
        {
            alert("end2 time must be after start2 time");
            return;
        }
        if ( start1 > end2 || start2 > end1 )
        {
            alert("There is NO overlap");
        } else {
            alert("There IS overlap");
        }
    }
    </script>
    </head>
    <body>
    <form>
    start1: <input name="starthr1" size="1">:<input name="startmn1" size="1"><br/>
    end1: <input name="endhr1" size="1">:<input name="endmn1" size="1"><br/>
    <br/>
    start2: <input name="starthr2" size="1">:<input name="startmn2" size="1"><br/>
    end2: <input name="endhr2" size="1">:<input name="endmn2" size="1"><br/>
    <br/>
    <input type="button" value="check the times" onclick="check(this.form);"/>
    </form>
    </body>
    </html>
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #4
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    Yes, your code is broken.

    Enter these values:
    Code:
    6    2
    7    30
    2    35
    4    23
    and see the answer "false"

    Then change the 6 to 4 so it reads
    Code:
    4    2
    7    30
    2    35
    4    23
    and it *STILL* reads false.

    Clearly there is no overlap in the top case but clearly there is in the bottom one. How can they both get the same answer?

    But when I change your code to
    Code:
    comp=(intime1 <= outtime2)&&(intime2 <= outtime1)
    as I thought then you get false and true, instead. As expected.

    I would say that you did inadequate testing of your solution, no?
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • Users who have thanked Old Pedant for this post:

    blaze4218 (10-07-2011)

  • #5
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    And just to rub it in...

    Which means (StartA <= EndB) And (EndA >= StartB)
    but then
    Code:
    comp=(intime1 <= outtime2)&&(outtime1 <= intime2)
    You didn't translate your own words into code, correctly.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #6
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    18,079
    Thanks
    203
    Thanked 2,542 Times in 2,520 Posts
    Glad to see that you are using my *1 method to convert a string value to a number!

    Here is my "improved" version incorporating input validation:-

    Code:
    <html>
    <head>
    <script>
    function check(form) {
    
    var sh1 = parseInt(form.starthr1.value);
    var eh1 = parseInt(form.endhr1.value);
    var sh2 = parseInt(form.starthr2.value);
    var eh2 = parseInt(form.endhr2.value);
    
    var sm1 = parseInt(form.startmn1.value);
    var em1 = parseInt(form.endmn1.value);
    var sm2 = parseInt(form.startmn2.value);
    var em2 = parseInt(form.endmn2.value);
    
    if (isNaN(sh1) || isNaN(sh2) || isNaN(eh1) || isNaN(eh2) || isNaN(sm1) || isNaN(sm2) || isNaN(em1) || isNaN(em2)){
    alert ("Enter numbers only in all the fields!");
    return false;
    }
    
    if (sh1 >23 || sh2>23 || eh1 >23 || eh2 >23 || sm1 >59 || sm2 >59 || em1 >59 || em2 >59) {
    alert ("Invalid times - hours must be 0-24, minutes 0-59");
    return false;
    }
    
        var start1 = sh1 * 60 + sm1;
        var end1   = eh1 * 60 + em1;
    
        var start2 = sh2 * 60 + sm2;
        var end2   = eh2 * 60 + em2;
    
        if ( start1 > end1 ) {
            alert("end1 time must be after start1 time");
            return false;
        }
        if ( start2 > end2 ) {
        alert("end2 time must be after start2 time");
        return false;
        }
        if ( start1 > end2 || start2 > end1 ) {  // if edges of time blocks may not overlap
    //  if ( start1 >= end2 || start2 >= end1 ) {  // if edges of time blocks may overlap e.g. same times e1 & s2
        alert ("There is NO overlap");
        } 
        else {
        alert ("There IS overlap");
        }
    }
    </script>
    </head>
    <body>
    <form>
    Start1: <input name="starthr1" size="1">:<input name="startmn1" size="1"><br/>
    End1:&nbsp <input name="endhr1" size="1">:<input name="endmn1" size="1"><br/>
    <br/>
    Start2: <input name="starthr2" size="1">:<input name="startmn2" size="1"><br/>
    End2:&nbsp <input name="endhr2" size="1">:<input name="endmn2" size="1"><br/>
    <br/>
    <input type="button" value="Check if the times overlap" onclick="check(this.form);"/>
    </form>
    </body>
    </html>
    Last edited by Philip M; 10-07-2011 at 08:20 AM. Reason: typo

    All the code given in this post has been tested and is intended to address the question asked.
    Unless stated otherwise it is not just a demonstration.

  • Users who have thanked Philip M for this post:

    blaze4218 (10-07-2011)

  • #7
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    LOL!!! Glad to see you can use parseInt when it's useful!

    Are we having fun, yet?

    <grin/>

    Bedtime for bonzo, here. G'night.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #8
    Regular Coder
    Join Date
    Apr 2005
    Location
    Texas
    Posts
    448
    Thanks
    24
    Thanked 63 Times in 63 Posts
    Glad to see you can use parseInt when it's useful!
    -Old Pedant, did you just mock me for the one thing I actually got right? Harsh dude...

    So if what you want is the IS OVERLAP condition
    - Is overlap, or isn't overlap, either will do. I could respond to if(overlap) just as easily as I could to if(!overlap). As long as I get a true or false.

    there's no need to get seconds. Getting just minutes (that is, multiplying the hours, only, by 60) is sufficient.
    - I started with seconds, but when I posted it I left them out to clean up my post a bit, I guess I left in the *60*60, oops.

    I can't tell from your names whethe "intime" means "start" or "end"
    -And I can't tell from your post whethe your pulling my chain or not... Yeah, "in time" meant "start"...

    You didn't translate your own words into code, correctly.
    -They weren't my words, that's why I was having such a hard time
    -I mentioned that the code I posted was actually the result of a typo, but that it seemed to work

    And just to rub it in...
    -Really?

    All defensive rants aside, thank you very much for that thorough analysis of how to map out an idea and code it properly. It was very helpful.
    @Philip M you didn't need to go through all that trouble with the input validation, I am appending this overlap checker to a script that already has input auto correction. But thank you very much for taking the time.

  • #9
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    Quote:
    Glad to see you can use parseInt when it's useful!
    -Old Pedant, did you just mock me for the one thing I actually got right? Harsh dude...
    No, no! That was directed at Philip!

    Philip has long been a proponent of not using parseInt() or parseFloat() or even Number(). He just multiplies a text value by 1 to convert it to a number. In this case, he really did want to check for integers, so he used parseInt. I was yanking his chain. Didn't you see his comment to me about multiplying by 1?

    I can't tell from your names whethe "intime" means "start" or "end"
    -And I can't tell from your post whethe your pulling my chain or not... Yeah, "in time" meant "start"...
    I figured that out after I finally actually installed your code and tested it. Sorry, should have gone back to change it.

    But I was thinking that you might have something like, say, a boat rental system. So "out time" means when the rental starts and "in time" means when it ends. Honest, names liike in and out could be interpreted either way, depending on the application.

    *********

    One real curiosity of mine: Why'd you use onkeyup in all those form fields? If somebody changes a value from, say, 11 to 6, in the process they will have to change 11 to 1, and that will give you a temporarily bogus result from your "compare". Wouldn't onchange have made more sense? On top of that, if you use the mouse-only to change a value, onkeyup will never get triggered. That was truly the only strange part of your code, to me. (Well, other than your love of IDs instead of names. <grin/>)
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #10
    Regular Coder
    Join Date
    Apr 2005
    Location
    Texas
    Posts
    448
    Thanks
    24
    Thanked 63 Times in 63 Posts
    Oh, yeah that makes sense about the *1 (I was wondering what he was talking about)
    About the ambiguity of intime outtime: That never really occurred to me, I was just thinking about the scope of my app, huh... My bad...

    To satisfy your curiosity: I think you and Philip missed out on the fact that I was only testing the viability of the algorithm (intime1 <= outtime2)&&(outtime1 <= intime2), and the code I presented was just a blank .html file i whipped up to test it. I only used the corrected algorithm and deleted the .html file...The actual project will use the overlap code to check values against arrays- triggered by the user clicking a button once all inputs have been entered...
    Code:
       function CHECK_FOR_OVERLAP(){
        for(var i in Selected.File){
         if(i!=Selected.entryIndex){			//omitt the selected entry from overlap check...Duh!
          start1 =  HHMMSS_TO_SECONDS(Selected.File[i][2]);
          end1 = HHMMSS_TO_SECONDS(Selected.File[i][5]);
          start2 = HHMMSS_TO_SECONDS(Selected.Entry[2]);
          end2 = HHMMSS_TO_SECONDS(Selected.Entry[5]);
          unique = ( start1 >= end2 || start2 >= end1 );
          if(!unique){valid=!1;return 'Error: The time you have entered overlaps with another time entry.';}
          }
         }
         return !1
        }
    My point being that for my own convenience in this temporary test html document, I decided to use onkeyup as the trigger so I could see the results in real time... I really have to watch what I ask here, you guys take my questions sooo literally
    Like Philip adding input validation. Although, I am positive that will be useful when someone finds this thread from a google search 6months from now...
    I also don't use forms very often, so I never knew that form.name.value was cross browser, when I first started out I found out the hard way that id.style.whatever wasn't cross browser, so I switched to document.getElementById('id').whatever for all direct element access and never looked back. But I don't think I'll be changing that anytime soon, I like using the same methodology across the board, and not just going back and forth...

    And if you think these are curiosities, I'd love to show you the full code you've been helping me with all week (i'm not posting it here though), you would probably get a kick out of all the noob logic lol.

  • #11
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    LOL re the form name stuff.

    When JS first started, the *ONLY* way to get to form fields was by name. Back in 1996 or 1997, I think (I didn't start with JS until 1998). MSIE didn't even have getElementById() in MSIE 4, for example. [It's why you still see some ancient JS code that does if ( document.all ) ... ... you could do document.all(id) in MSIE versus document.getElementById(id) in Netscape 4.]

    The other reasons to use names for form fields:
    (1) It's a tad faster to do form.name because the number of elements in the <form> collection is liable to be a lot smaller than the number of id's in an entire page. Granted, since most JS implementations use hash table lookup for both names and ids it might be roughly the same speed, but it's almost surely not slower.
    (2) If you do any server-side work at all, you know that any <form> field that does *NOT* have a name is INVISIBLE to the server side code. That's because when you submit a <form> from HTML, only fields with names (and only fields that are not disabled, by the by) will have their values included in the query string (for method=get) or post data (for method=post).

    So...for me, where 98% of what I do is submit pages to server-side code, names are the only way to go.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #12
    Regular Coder
    Join Date
    Apr 2005
    Location
    Texas
    Posts
    448
    Thanks
    24
    Thanked 63 Times in 63 Posts
    any <form> field that does *NOT* have a name is INVISIBLE to the server side code
    I use names, I just don't access the element from javascript via the name

  • #13
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    25,895
    Thanks
    79
    Thanked 4,421 Times in 4,386 Posts
    Yes, I realize that. I was laughing about your worrying that they might not be cross-browser compatible. In truth, the are the about the only thing that *is* fully cross-browser compatible, all the way back to even before JavaScript was introduced but certainly including the very first versions of JavaScript. (Or, more properly, of the concept of DOM.) I would trust name access before I'd trust ID access to be 100% compatible.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #14
    Supreme Master coder! Philip M's Avatar
    Join Date
    Jun 2002
    Location
    London, England
    Posts
    18,079
    Thanks
    203
    Thanked 2,542 Times in 2,520 Posts
    [QUOTE=blaze4218;1144836]Like Philip adding input validation. Although, I am positive that will be useful when someone finds this thread from a google search 6months from now...
    QUOTE]

    Yes, that was my intention.

    All the code given in this post has been tested and is intended to address the question asked.
    Unless stated otherwise it is not just a demonstration.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •