Tip: Finding scheduling conflicts

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Tip: Finding scheduling conflicts

4D Tech mailing list
Ever had to do date math where you need to detect conflict schedules?
Recently, I had to do some data analysis that involved checking for
potential conflicts in a schedule, counting them, and figuring out how big
the conflicts were. This isn't a live schedule, it's historical scheduling
data used to model future demand against available resources. The idea is
to surface obvious material shortfalls. If you were an event planner, you
might use October 2016 demand to project 2017 demand to see if you have
enough chairs, caterers, dancing bears, clowns, kegs of beer, etc.
available. \Of course, scheduling efficiency and other constraints might be
issues, but that's not what this model is working on...it's trying to
measure fixed inventory against projected demand to see if more inventory
is needed. Right, too much backstory...welcome to me.

Anyway, I've always "hated" date math. As it turns out, I just wasn't
looking for existing solutions efficiently and I don't hate date math at
all now. It didn't take long to find out that time interval calculations
have been studied exhaustively as have algorithms for doing conflict
detection, optimal fitting, etc. In my case, I just need a couple of things:

* Do these two time ranges intersect?
* By how much?

My particular problem takes more than that to sort out, and I also do
another form of projection that's a tweak on this, but that's the nub of
the interval math right there. As a highlight of what I'm talking about,
here are some comments adapted from a StackOverflow post on the subject:

// Great explanation on StackOverflow here:
//
https://stackoverflow.com/questions/143552/comparing-date-ranges/143568#143568

// Best. Ascii. Diagram. Ever. This blocks out eleven possible interval
comparison outcomes.
// I've added discussion of two special cases and show what catches them.
-- DPA

//            |-------------------|          compare to this one
//                |---------|                contained within
//            |----------|                   contained within, equal start
//                    |-----------|          contained within, equal end
//            |-------------------|          contained within, equal
start+end
//      |------------|                       not fully contained, overlaps
start
//                    |---------------|      not fully contained, overlaps
end
//      |-------------------------|          overlaps start, bigger
//            |-----------------------|      overlaps end, bigger
//      |------------------------------|

// on the other hand, let me post all those that don't overlap:
//
//            |-------------------|          compare to this one
//      |---|                                ends before
//                                  |---|    starts after

// Notes about two possibly confusing cases
//            |-------------------|          compare to this one
//      |-----|                              ends at start is a case of
//      |------------|                       not fully contained, overlaps
start

//            |-------------------|          compare to this one
//                                |-----|    starts at end is a case of
//                    |---------------|      not fully contained, overlaps
end



Below I'm posting a method for calculating the overlap between two time
ranges in seconds. A few notes:

* All of this code assumes and requires date times on a consistent
timezone. If you do a lot of datetime stuff and haven't already moved
everything to Zulu with offsets stored somewhere for display purposes, your
making your life needlessly hard. But all this code requires is that
datetimes are on the same time zone, whatever that is.

* Midnight is just another moment like any other, with datetimes, midnight
doesn't take any special consideration.

* The routine has minimal error checking on the parameters. It chokes on
end times earlier than start times and that's it. It doesn't detect 0000
type times and those might screw you up.

* There are a bunch of subroutines listed that I'm not posting. Most folks
will have their own versions or use a different style that doesn't require
some of my subroutines. (I'm big on parameter checking, most people aren't.)

* I didn't write the date time utilities and haven't even looked at them.
They work, that's all I know.

* I've also included a manual test routine that works in conjunction with
the main method. Good luck trying to do something like this without a test
case that you can run over an over until all of the bugs quit moving. Stay
down bug! Just stay down!

* Speaking of bugs, if anyone finds one (or more), PLEASE tell me. Ideally,
fix it and tell me...but at least tell me/the list.

* If anyone from 4D, etc. ever wants to clean this up and make it into a
tech note, please post a link when it's published. I'd use it!

* If all you need is to detect that two appointments overlap and don't care
by how much, see the notes. It's eaasier to figure than you might expect -
I put the relevant comprisons at the top of my big case of scenarios below.

* You'll find lots of notes and some great ASCII charts throughout. I give
credit to where I found everything.

* Tip: If this approach isn't good enough for you and you're after optimal
schedule detection (least CPU use), the data structure you want to look for
is an "interval tree." Just google scheduling conflicts and interval trees
and you'll be eyeballs-deep into big O notation before you can blink.
Here's a link to a decent summary:

http://www.geeksforgeeks.org/given-n-appointments-find-conflicting-appointments/

I'm not doing anything intensive enough to need interval trees here (I'm
not schedule fitting, just counting stuff), but if you have a big
scheduling system with lots of conflict detection, check out interval
trees. (Not that list processing is easy or pleasurable in 4D, but you can
do it.)

Okay, here is the method and the test method to match.

If (False)  // ===========================================
utl_DTS_GetIntervalOverlapSecs
 // DESCRIPTION: Returns overlap of date time stamps, if any.
 // Result is -1 if you pass bad inputs.
 // All inputs are date time stamps.
 // Notes:
 // There's a always a question of how to treat a case where the
 // end time of one interval is the start time of the other. In this case,
 // I've gone with treating it as an overlap when the boundaries touch.
 // This can be revisited if we need something different.
 // Great explanation on StackOverflow here:
 //
https://stackoverflow.com/questions/143552/comparing-date-ranges/143568#143568
 // Best. Ascii. Diagram. Ever. This blocks out eleven possible interval
comparison outcomes.
 // I've added discussion of two special cases and show what catches them.
-- DPA
 //            |-------------------|          compare to this one
 //                |---------|                contained within
 //            |----------|                   contained within, equal start
 //                    |-----------|          contained within, equal end
 //            |-------------------|          contained within, equal
start+end
 //      |------------|                       not fully contained, overlaps
start
 //                    |---------------|      not fully contained, overlaps
end
 //      |-------------------------|          overlaps start, bigger
 //            |-----------------------|      overlaps end, bigger
 //      |------------------------------|
 // on the other hand, let me post all those that don't overlap:
 //
 //            |-------------------|          compare to this one
 //      |---|                                ends before
 //                                  |---|    starts after
 // Notes about two possibly confusing cases
 //            |-------------------|          compare to this one
 //      |-----|                              ends at start is a case of
 //      |------------|                       not fully contained, overlaps
start
 //            |-------------------|          compare to this one
 //                                |-----|    starts at end is a case of
 //                    |---------------|      not fully contained, overlaps
end
 //
 // The point of the art above is to show the possibilities, and to show a
shortcut
 // to figuring out "do these overlap?" Only 'ends before' and 'starts
after' aren't
 // overlaps. In other words, everything else is an overlap - even if by
only 0 seconds.
 // In this method here, what we're trying to calculate are
 // the number of seconds of overlap, so all need to be covered explicitly.
 // The Wikipedia entry on Allen's interval algebra (what we're doing):
 // https://en.wikipedia.org/wiki/Allen%27s_interval_algebra
 // Dang, there's an entire book on time-data oriented SQL:
 // https://www2.cs.arizona.edu/people/rts/tdbbook.pdf
 // Note:
 // * You can _definitely_ reduce the number of comparisons in this method
by collapsing and shortcutting
 //   some of the comparisons. I was doing that, then I switched to this
more explicit code. Your call.
 // * Not everyone counts the possible combinations the same way.
 // * You'll need to decide if you want times that overlap exactly to be
considered matching or not.
 //  For example, it's normal to say "this appointment runs from 9-10 and
the next one from 10-11."
 //  In normal language, Those don't overlap because you treat them as
09:00-09:59:59 and 10:00:00-10:59:59.
 // This routine treats 10-11 and 11-12 as overlapping but by 0 seconds.
There are some notes above about
 // where these catch in the code, if you want to tweak the behavior.
 // See test routine
utl_DTS_Overlap_Test
 // CREATED BY: David Adams
 // DATE: 01/07/2017
 // LAST MODIFIED:
End if   // ============================================

C_LONGINT($0;$overlap_seconds)  // Could change to return a descriptor or
error.
C_TEXT($1;$range_start_dts)
C_TEXT($2;$range_end_dts)
C_TEXT($3;$check_start_dts)
C_TEXT($4;$check_end_dts)

$overlap_seconds:=-1  // Result is ambiguous if you pass bad inputs.

C_TEXT($error_name)
$error_name:=MethodCheck_ParameterCount (Count parameters;4;4)
If ($error_name="")
$range_start_dts:=$1
$range_end_dts:=$2
$check_start_dts:=$3
$check_end_dts:=$4
Case of
: ($range_start_dts>$range_end_dts)  // Start after end? Bad input.
$error_name:="BadDTS_StartsAfterEnding"
: ($check_start_dts>$check_end_dts)  // Start after end? Bad input.
$error_name:="BadDTS_StartsAfterEnding"
End case
If ($error_name#"")
C_TEXT($diagnostic_text)
$diagnostic_text:=""
$diagnostic_text:=$diagnostic_text+"$range_start_dts =
"+$range_start_dts+Char(Carriage return)
$diagnostic_text:=$diagnostic_text+"$range_end_dts =
"+$range_end_dts+Char(Carriage return)
$diagnostic_text:=$diagnostic_text+"$check_start_dts =
"+$check_start_dts+Char(Carriage return)
$diagnostic_text:=$diagnostic_text+"$check_end_dts =
"+$check_end_dts+Char(Carriage return)
ErrorStack_AddOnError ($error_name;Current method name;$diagnostic_text)
End if
End if

If ($error_name="")
C_LONGINT($check_length)  // We use this a few places below.
$check_length:=utl_DT_Difference_Seconds ($check_end_dts;$check_start_dts)
Case of
: ($check_end_dts<$range_start_dts)  // Ends before: NO conflict
 //            |-------------------|          compare to this one
 //      |---|                                ends before
$overlap_seconds:=0
: ($check_start_dts>$range_end_dts)  // Ends after: NO Conflict
 //            |-------------------|          compare to this one
 //                                  |---|    starts after
 //
$overlap_seconds:=0
 //---------------------------------------------------------------------------
 // All other nine possible cases represent an overlap of some length.
 //---------------------------------------------------------------------------
: (($check_start_dts>$range_start_dts) & ($check_end_dts<$range_end_dts))
 // Contained within
 //            |-------------------|          compare to this one
 //                |---------|                contained within
$overlap_seconds:=$check_length
: (($check_start_dts=$range_start_dts) & ($check_end_dts<$range_end_dts))
 // contained within, equal start
 //            |-------------------|          compare to this one
 //            |----------|                   contained within, equal start
$overlap_seconds:=$check_length
: (($check_start_dts>$range_start_dts) & ($check_end_dts=$range_end_dts))
 //            |-------------------|          compare to this one
 //                    |-----------|          contained within, equal end
$overlap_seconds:=$check_length
: (($check_start_dts=$range_start_dts) & ($check_end_dts=$range_end_dts))
 //            |-------------------|          compare to this one
 //            |-------------------|          contained within, equal
start+end
$overlap_seconds:=$check_length
: (($check_start_dts<$range_start_dts) & ($check_end_dts<$range_end_dts))
 //            |-------------------|          compare to this one
 //      |------------|                       not fully contained, overlaps
start
 //      |-----|                              ends at start
$overlap_seconds:=utl_DT_Difference_Seconds
($check_end_dts;$range_start_dts)
: (($check_start_dts>$range_start_dts) & ($check_end_dts>$range_end_dts))
 //            |-------------------|          compare to this one
 //                    |---------------|      not fully contained, overlaps
end
$overlap_seconds:=utl_DT_Difference_Seconds
($range_end_dts;$check_start_dts)
: (($check_start_dts<$range_start_dts) & ($check_end_dts=$range_end_dts))
 //            |-------------------|          compare to this one
 //      |-------------------------|          overlaps start, bigger
$overlap_seconds:=$check_length
: (($check_start_dts=$range_start_dts) & ($check_end_dts>$range_end_dts))
 //            |-------------------|          compare to this one
 //            |-----------------------|      overlaps end, bigger
$overlap_seconds:=$check_length
: (($check_start_dts<$range_start_dts) & ($check_end_dts>$range_end_dts))
 //            |-------------------|          compare to this one
 //      |------------------------------|     overlaps entire period
$overlap_seconds:=$check_length
Else   // Starts during
TRACE  // If you're reading this note, I screwed up.
End case
End if

$0:=$overlap_seconds

And now the test method:

If (False)  // ===========================================
utl_DTS_Overlap_Test
 // DESCRIPTION: Tests if date times overlap at all.
 // All inputs are date time stamps.
 // Checking my work here...
 // CREATED BY: David Adams
 // DATE: 01/07/2017
 // LAST MODIFIED:
End if   // ============================================


C_TEXT($dts_9am)
C_TEXT($dts_10am)
C_TEXT($dts_11am)
C_TEXT($dts_12_noon)
C_TEXT($dts_1pm)
C_TEXT($dts_2pm)
C_TEXT($dts_3pm)
C_TEXT($dts_4pm)
C_TEXT($dts_5pm)
$dts_9am:=utl_DT_Get (!2018-01-01!;?09:00:00?;True)
$dts_10am:=utl_DT_Get (!2018-01-01!;?10:00:00?;True)
$dts_11am:=utl_DT_Get (!2018-01-01!;?11:00:00?;True)
$dts_12_noon:=utl_DT_Get (!2018-01-01!;?12:00:00?;True)
$dts_1pm:=utl_DT_Get (!2018-01-01!;?13:00:00?;True)
$dts_2pm:=utl_DT_Get (!2018-01-01!;?14:00:00?;True)
$dts_3pm:=utl_DT_Get (!2018-01-01!;?15:00:00?;True)
$dts_4pm:=utl_DT_Get (!2018-01-01!;?16:00:00?;True)
$dts_5pm:=utl_DT_Get (!2018-01-01!;?17:00:00?;True)

C_TEXT($cr)
C_TEXT($tab)
C_TEXT($results)
$cr:=Char(Carriage return)
$tab:=Char(Tab)

$results:=""
$results:=$results+"Description"+$tab
$results:=$results+"Code"+$tab
$results:=$results+"Errors Expected"+$tab
$results:=$results+"Errors"+$tab
$results:=$results+"Seconds Expected"+$tab
$results:=$results+"Seconds"+$cr

C_LONGINT($overlap_seconds)

  //            |-------------------|          compare to this one
  //                |---------|                contained within
  //            |----------|                   contained within, equal start
  //                    |-----------|          contained within, equal end
  //            |-------------------|          contained within, equal
start+end
  //      |------------|                       not fully contained,
overlaps start
  //                    |---------------|      not fully contained,
overlaps end
  //      |-------------------------|          overlaps start, bigger
  //            |-----------------------|      overlaps end, bigger
  //      |------------------------------|     overlaps entire period
  //      |---|                                ends before
  //                                  |---|    starts after
  //      |-----|                              ends at start (caught by
'not fully contained, overlaps start')
  //                                |-----|    starts at end (caught by
'not not fully contained, overlaps end')


  // utl_DTS_GetIntervalOverlapSecs (Range start;Range end;Test start;Test
end) : Seconds with -1 for bad input error

If (True)  // Bad input cases.
ErrorStack_ClearStack
$results:=$results+"Bad range input"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_9am;$dts_12_noon;$dts_1pm)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_9am;$dts_12_noon;$dts_1pm)"+$tab
$results:=$results+"1"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+"-1"+$tab
$results:=$results+String($overlap_seconds)+$cr
ErrorStack_ClearStack
$results:=$results+"Bad check input"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_9am;$dts_3pm;$dts_1pm;$dts_12_noon)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_9am;$dts_3pm;$dts_1pm;$dts_12_noon)"+$tab
$results:=$results+"1"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+"-1"+$tab
$results:=$results+String($overlap_seconds)+$cr
End if

  //            |-------------------|          compare to this one
  //                |---------|                contained within
ErrorStack_ClearStack
$results:=$results+"Contained within"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_11am;$dts_12_noon)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_11am;$dts_12_noon)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr


  //            |-------------------|          compare to this one
  //            |----------|                   contained within, equal start
ErrorStack_ClearStack
$results:=$results+"Contained within, equal start"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_10am;$dts_11am)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_11am;$dts_11am)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr

  //            |-------------------|          compare to this one
  //                    |-----------|          contained within, equal end
ErrorStack_ClearStack
$results:=$results+"Contained within, equal end"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_2pm;$dts_3pm)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_2pm;$dts_3pm)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr



  //            |-------------------|          compare to this one
  //            |-------------------|          contained within, equal
start+end
ErrorStack_ClearStack
$results:=$results+"Contained within, equal start+end"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_11am;$dts_10am;$dts_11am)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_11am;$dts_10am;$dts_11am)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr


  //            |-------------------|          compare to this one
  //      |------------|                       not fully contained,
overlaps start
ErrorStack_ClearStack
$results:=$results+"Not fully contained, overlaps start"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_9am;$dts_11am)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_9am;$dts_11am)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr


  //            |-------------------|          compare to this one
  //                    |---------------|      not fully contained,
overlaps end
ErrorStack_ClearStack
$results:=$results+"Not fully contained, overlaps end"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_2pm;$dts_4pm)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_3pm;$dts_2pm;$dts_4pm)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(60*60)+$tab
$results:=$results+String($overlap_seconds)+$cr


  //            |-------------------|          compare to this one
  //      |---|                                ends before
ErrorStack_ClearStack
$results:=$results+"Ends before"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_11am;$dts_3pm;$dts_9am;$dts_10am)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_11am;$dts_3pm;$dts_9am;$dts_10am)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(0)+$tab
$results:=$results+String($overlap_seconds)+$cr

  //            |-------------------|          compare to this one
  //                                  |---|    starts after
ErrorStack_ClearStack
$results:=$results+"Ends after"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_3pm;$dts_4pm)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_3pm;$dts_4pm)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(0)+$tab
$results:=$results+String($overlap_seconds)+$cr


  //            |-------------------|          compare to this one
  //      |-----|                              ends at start
ErrorStack_ClearStack
$results:=$results+"Ends at start"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_9am;$dts_10am)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_9am;$dts_10am)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(0)+$tab
$results:=$results+String($overlap_seconds)+$cr

  //            |-------------------|          compare to this one
  //                                |-----|    starts at end
ErrorStack_ClearStack
$results:=$results+"Starts at end"+$tab
$overlap_seconds:=utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_2pm;$dts_3pm)
$results:=$results+"utl_DTS_GetIntervalOverlapSecs
($dts_10am;$dts_2pm;$dts_2pm;$dts_3pm)"+$tab
$results:=$results+"0"+$tab
$results:=$results+String(ErrorStack_Count )+$tab
$results:=$results+String(0)+$tab
$results:=$results+String($overlap_seconds)+$cr

SET TEXT TO PASTEBOARD($results)// I usually set a breakpoint before or
after this.
**********************************************************************
4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4d.com/archives.html
Options: http://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:[hidden email]
**********************************************************************
Reply | Threaded
Open this post in threaded view
|

Re: Tip: Finding scheduling conflicts

4D Tech mailing list
For those of you following along at home or checking the archives in days
to come, I came across a really good lecture on interval trees:

https://www.youtube.com/watch?v=q0QOYtSsTg4

It's presented by Robert Sedgewick. Yes, *that* Robert Sedgewick, the
algorithms guy. Well, the algorithms guy for people like me that just don't
have the background for Knuth. The lecture isn't enough to just run and
implement interval trees, but it does explain really well the basic concept
and illustrates exactly why it's such a powerful and tidy way to handle
interval searches.

Fair warning: If you don't understand binary search trees and how to build
and maintain them by hand, it probably won't make sense. If you do know
that already, the interval tree is a BST with some augmentation. When you
insert, you walk back up and attach some extra information to the node to
indicate the max value along the subtree path. (Likewise, you would have to
reset this value if you deleted the max element.) This small amount of
hinting costs a bit during insert/delete, but then saves you having to scan
parts of branches or even whole branches when searching. It's kind of
genius.

So, for anyone with an interest in this subject, check it out. The ultimate
benefit of this simple+powerful data structure is that insert/search/delete
are guaranteed to run in log N instead of N time. That's huge. That's what
you get from binary trees normally. Sedgewick says that the runtime for
finding all interval intersections is R log N, which is a huge advantage
over the alternative of N. It's just a massive, massive optimization.

This is a fairly specific problem, granted, but if your'e doing schedule
fitting, schedule/capacity analysis...or anything having to do with
intervals, this algorithm is the real deal. I'm talking about datetime
intervals, but intervals are any start-endpoint pair on a numberline, there
are lots of things like that other than date times.

P.S. For any Postgres fans, check out tsrange with a GIST index and the
OVERLAP operator. Subsecond results for scheduling range conflict
management with lots of rows.
**********************************************************************
4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4d.com/archives.html
Options: http://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:[hidden email]
**********************************************************************
Reply | Threaded
Open this post in threaded view
|

Re: Tip: Finding scheduling conflicts

4D Tech mailing list
I'm back to tell you about a wonderful thing called "the Internet" ;-) I
turns out that Sedgewick has a series of free courses at Coursera:

https://www.coursera.org/courses?languages=en&query=sedgewick

What I linked to yesterday comes from Algorithms 1. I checked the syllabus
and it looks like a really thorough introductions to algorithms and data
structures course.

It's pretty mind-blowing that you can get all of this for free from Robert
Sedgewick. Decades back, everyone had Knuth's "The Art of Computer
Programming." I just didn't (don't) have the math or the C to follow it.
Sedgewick had an excellent smaller book called Algorithms with examples in
Pascal, which is very easy to read if you're used to 4D. Sedgewick is
admirable in his ability to make complex subjects comprehensible.

I just noticed on Wikipedia that Knuth supervised Sedgewick's doctorate,
and that Sedgewick co-invented Red/Black Trees (a BST variant with some
optimizations for some applications.)

So, an amazing free resource out there...
**********************************************************************
4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4d.com/archives.html
Options: http://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:[hidden email]
**********************************************************************
Reply | Threaded
Open this post in threaded view
|

Re: Tip: Finding scheduling conflicts

4D Tech mailing list
David,

On Wed, Aug 30, 2017 at 2:37 PM, David Adams via 4D_Tech <
[hidden email]> wrote:

> I'm back to tell you about a wonderful thing called "the Internet" ;-) I
> turns out that Sedgewick has a series of free courses at Coursera:
>
> https://www.coursera.org/courses?languages=en&query=sedgewick
>
> What I linked to yesterday comes from Algorithms 1. I checked the syllabus
> and it looks like a really thorough introductions to algorithms and data
> structures course.
>

​Coursera is sort of remarkable in this way.

My only hesitation is all the work has to be submitted in JAVA - which I
really don't know. ​Maybe someone here who does know JAVA would enroll and
a group of interested 4D devs could do a hangout or something to
participate as a group?


--
Kirk Brooks
San Francisco, CA
=======================

*The only thing necessary for the triumph of evil is for good men to do
nothing.*

*- Edmund Burke*
**********************************************************************
4D Internet Users Group (4D iNUG)
FAQ:  http://lists.4d.com/faqnug.html
Archive:  http://lists.4d.com/archives.html
Options: http://lists.4d.com/mailman/options/4d_tech
Unsub:  mailto:[hidden email]
**********************************************************************