Overlap of two closed intervals

[noknok]

Given two closed intervals
x = [x0,x1] and y = [y0,y1]

(By a "closed interval" I mean a pair [z0,z1] with z0 <= z1, which
denotes the set of all (real number) values z with z0 <= z <=z1.)

I need to implement the boolean result function
overlap(x,y)
which returns "true", if x and y have common points (i.e. their
intersection is not empty), and "false" otherwise.

I suggest the following implementation:
overlap(x,y) := if ((x0<=y0<=x1) or (x0<=y1<=x1) or (y0<=x0<=y1) or
(y0<=x1<=y1)) then "true" else "false"
I assume, that's correct.

But is it the shortest and most effective implementation?

[Han de Bruijn]

If you want to avoid a separate test on (x0 <= x1) and (y0 <= y1),
I'd rather suggest for the "true" part OR's the more symmetrical:

x0 <= y0 <= x1 <= y1
x0 <= y0 <= y1 <= x1
y0 <= x0 <= x1 <= y1
y0 <= x0 <= y1 <= x1

Han de Bruijn

[Richard Tobin]

In article <519a520c-af18-4616...@k7g2000yqj.googlegroups.com>,
noknok <bucepha...@gmail.com> wrote:

>Given two closed intervals
> x = [x0,x1] and y = [y0,y1]

>I need to implement the boolean result function

> overlap(x,y)
>which returns "true", if x and y have common points (i.e. their
>intersection is not empty), and "false" otherwise.

They overlap if they are not disjoint. If they are disjoint,
either x is to the left of y (i.e. x1 < y0) or it is to the right
of y (i.e. x0 > y1).

So they overlap if x1 >= y0 and x0 <= y1.

-- Richard

[noknok]

Eureka!
Thank you Han de Bruijn, thank you Richard!
Richards suggestion can't be beaten, I suppose, that's nice and short.
What a shame, that I couldn't come up with it myself!
Thank you very much, indeed!

[Han de Bruijn]

Agreed. My SQL query shall be simplified too with Richards suggestion.

Han de Bruijn

[Han de Bruijn]

To find all employees with jobs overlapping in time we do:

select A.emplid
, A.empl_rcd -- job A ID
, B.empl_rcd -- job B ID
, A.effdt -- x0
, A.enddt -- x1
, B.effdt -- y0
, B.enddt -- y1
from job A
, job B
where (A.emplid = B.emplid)
and (A.effdt <= A.enddt)
and (B.effdt <= B.enddt)
and (B.effdt <= A.enddt)
and (A.effdt <= B.enddt)
-- and (A.primary_key < B.primary_key)
order by A.emplid
/

But this query gives all equal jobs and jobs in reverse order as well.
In order to get rid of the duplicates and trivialities, we should add
a primary key (or use an existing composite key that is unique). Then
out-comment the last-minus-two line.

Han de Bruijn

[Tony Orlow]

false if x0>y1 or y0>x1, else true.

Tony

[Han de Bruijn]

Sure, Tony, and that is equivalent with what has been said already, by
Richard Tobin:

> So they overlap if x1 >= y0 and x0 <= y1.

i.e. true if (x0 <= y1) and (x1 >= y0), else false.

Han de Bruijn