Determining if a time falls within a given set of time intervals.

[DanBWeb]

Hi (using javascript) -

I have a schedule divided into periods
Period 1: 8:00 am - 9:10
Period 2: 9:15 am - 10:00 am
Period 3: 10:15 am - 11:05 am
...
...
...
Remember your days in school?..:)

I have a login time and a logout time (login at 8:10 am and logout at 9:45 am)

I need to know
1.) what period they logged in,
2.) what period they logged out and
3.) if they missed more than 25 minutes of any period

I am assuming I would build an array of start and end times for the periods, but after that I dont even know where to start. Any advice or ides would be greatly appreciated!

Dan B

[pbmods]

Changed thread title to better describe the problem (did you know that threads whose titles do not follow the Posting Guidelines actually get FEWER responses?).

[pbmods]

Heya, Dan.

Convert each of your time strings into a Date object:

var periods =
[
    { 'time': new Date('2007-01-01 08:00:00').getTime(), 'period': 1, 'start': true },
    { 'time': new Date('2007-01-01 09:10:00').getTime(), 'period': 1, 'start': false },
    .
    .
    .
];
 

And so on. The date that you use ('2007-01-01') is not important, as long as you use the same one for each period.

Then convert your login/logout times to Dates similarly.

Date::getTime() returns a Unix timestamp, which is just an integer, which makes it easy to use standard comparison operators (>, <, etc.).

All you have to do then is run a couple of binary searches through periods until you find the first element in periods where periods[i].time <= login and the first element in periods where periods[i].time >= logout.

Using the results of the search, you now know during which period the User logged in and during which period the User logged out. You also know the start and end times of the periods closest to the User's login/logout times so that you can tell if the User logged in late.

Note that you also know if the User logged in and/or out *during* a period, or if he did it during a break.

[DanBWeb]

"All you have to do then is run a couple of binary searches through periods until you find the first element in periods where periods[i].time <= login and the first element in periods where periods[i].time >= logout."

Can you give an example?

Thanks,

Dan B

[pbmods]

Heya, Dan.

Suppose you had a sorted Array (it has to be sorted; this is key):

var theArray = new Array(1, 4, 9, 16, 25, 36);
 

Also suppose you had a value, and you wanted to determine which number was the first one that came before your value:

var testStart = 8;
var testEnd = 18;
 

Now looking at the array, 4 is the number just before testStart, and 25 is the number just after testEnd. It's easy enough for us humans to figure that part out. Now how to go about making the computer see it.

The idea behind a binary search is 'divide and conquer'. By dividing a *sorted* array in half each time, we can readily eliminate 1/2 of the remaining array each time. The end result is that we know exactly where the item 'fits' very quickly.

There's a bit of a trick because for one number (in this case, testStart), we need to know which number is smaller than our test value, but we need to know which number is larger than our test value.

Ok. Let's get started.

In order to 'divide' the Array, we need to define our boundaries:

var min = 0;
var max = theArray.length - 1;
 
var foundStart = false;
 
/***************
*
*    Quick checks:
*/
if( testStart < theArray[min] )
{
    /***************
    *
    *    Start occurs before the array starts, which means that there is no value in theArray that is < foundStart.
    */
    foundStart = null;
}
else if( testStart > theArray[max] )
{
    /***************
    *
    *    Start occurs after the array ends, which means that the last value in theArray is the largest value that is < foundStart.
    */
    foundStart = theArray[max];
}
else
{
    /***************
    *
    *    Begin divide and conquer.
    */
    do
    {
        var target = Math.floor((min + max) / 2);
 
        if( testStart == theArray[target] )
        {
            /***************
            *
            *    This one's easy.
            */
            foundStart = theArray[target];
            break;
        }
        else if( testStart > theArray[target] )
        {
            /***************
            *
            *    testStart occurs after theArray[target].  Divide theArray to eliminate all values before target.
            */
            min = target;
        }
        else
        {
            /***************
            *
            *    testStart occurs before theArray[target].  Divide theArray to eliminate all values after target.
            */
            max = target;
        }
 
        /***************
        *
        *    Continue dividing the array until it is indivisible.
        */
    }
    while( (max - min) > 1 );
 
    /***************
    *
    *    At this point, either foundStart has been set (teststart == theArray[target]), or we have divided theArray to the point where we know which elements testStart fits in between.
    */
    if( foundStart === false )
    {
        /***************
        *
        *    Since we are looking for the first value that is < testStart, we use the min boundary.
        */
        foundStart = theArray[min];
    }
}
 

Let's work through this:

• testStart = 8, min = 0, max = 5 (6 - 1)
• Since 8 !< 1 (testStart !< theArray[min]), we know that foundStart cannot be null.
• Since 8 !> 36 (testStart !> theArray[max]), we know that foundStart cannot be 36.
• Begin divide and conquer:
  • target = Math.floor((0 + 5) / 2) => 2; theArray[2] = 9
  • 8 != 9 (testStart != theArray[2]), so continue.
  • 8 !> 9 (testStart !> theArray[2]), so continue.
  • max = 2 (max = target) because we know that 8 has to be < 9 since it's != and !>.
• Since 2 - 0 > 1 (max - min > 1), re-iterate.
  • target = Math.floor((0 + 2) / 2) => 1; theArray[1] = 4
  • 8 != 9, so continue.
  • 8 is > 9, so min = 1
  • 2 - 1 !> 1, so break the loop.
• foundStart is false (because testStart never == theArray[target]), so use theArray[min].
• foundStart = 4

Let's try it on the other end of the array. Suppose testStart = 25.

• min = 0, max = 5, foundStart = false
• 25 !< 1 (testStart !< theArray[min])
• 25 !> 36 (testStart !> theArray[max])
• loop:
  • target = Math.floor((0 + 5) / 2) => 2, theArray[target] = 9
  • 25 != 9 (testStart != theArray[target])
  • 25 is > 9, so min = 2 (testStart is > theArray[target], so min = target)
• 5 - 2 is > 1 (max - min is > 1), so re-iterate.
  • target = Math.floor((2 + 5) / 2) => 3, theArray[target] = 16
  • 25 != 16
  • 25 is > 16, so min = 3
• 5 - 3 is > 1, so re-iterate.
  • target = Math.floor((3 + 5) / 2) => 4, theArray[target] = 25
  • 25 == 25, so foundStart = 25. Break out of the loop.
• foundStart is not false, so we're done.
• foundStart = 25

To search for foundEnd, simply reverse the signs so that you set max when testEnd < theArray[target] and min when testEnd > theArray[target].