...

View Full Version : Determine Whether Two Time Ranges Overlap



blaze4218
10-07-2011, 05:52 AM
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/325933/determine-whether-two-date-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:


<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...

Old Pedant
10-07-2011, 07:04 AM
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.


-----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:


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:


....(True if StartA > EndB) ... (True if EndA < StartB) ...

I just find it easier to visualize if I write it as


There is NO OVERLAP if (StartA > EndB OR StartB > EndA)

And, yes, you *can* apply deMorgan's law to imply


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


There IS OVERLAP if ( ! (StartA > EndB OR StartB > EndA) )

or even, using JavaScript for OR:


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:


This IS OVERLAP if (StartA <= EndB AND StartB <= EndA)

comp=(intime1 <= outtime2)&&(outtime1 <= intime2)

Looks to me like yours should be


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??

Old Pedant
10-07-2011, 07:17 AM
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.


<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>

Old Pedant
10-07-2011, 07:27 AM
Yes, your code is broken.

Enter these values:


6 2
7 30
2 35
4 23

and see the answer "false"

Then change the 6 to 4 so it reads


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

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?

Old Pedant
10-07-2011, 07:31 AM
And just to rub it in...



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

but then


comp=(intime1 <= outtime2)&&(outtime1 <= intime2)

You didn't translate your own words into code, correctly.

Philip M
10-07-2011, 07:48 AM
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:-


<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>

Old Pedant
10-07-2011, 08:11 AM
LOL!!! Glad to see you can use parseInt when it's useful!

Are we having fun, yet?

<grin/>

Bedtime for bonzo, here. G'night.

blaze4218
10-07-2011, 03:36 PM
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.

Old Pedant
10-07-2011, 07:25 PM
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/>)

blaze4218
10-07-2011, 08:05 PM
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...


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 :D
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.

Old Pedant
10-07-2011, 08:45 PM
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.

blaze4218
10-07-2011, 09:03 PM
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

Old Pedant
10-08-2011, 02:38 AM
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.

Philip M
10-08-2011, 08:28 AM
[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. :)



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum