Java Chatter and Random Nagging

Friday, November 24, 2006

Detecting period overlap

The application I am working on in my day job needed a feature which required detecting date overlap. After first trying the straightforward approach, which were far more boolean operations than I wanted, I stumbled upon the solution, which surprised me by its beautiful logic so I would love to share it.

The problem :
Given are two periods in time boundaried by two dates :
22 nov 2006 till 25 nov 2006(p1.from, p1.till)
from 18 nov 2006 till 23 nov 2006(p2.from, p2.till)

Now, how do we detect whether an overlap exists between these two periods ?

The Solution :
There are four different cases of overlap :The straightforward solution to this problem would require quite some boolean logic to check whether a certain period overlaps, since there are four possibilities. It would require a logic like :

(p2.from < p1.from) && (p2.till < p1.from) ||
(p2.till > p1.till) && (p2.from < p1.till) ||

to incorporate all overlapping cases in one boolean check.

However, as you can see on the figure, there are only two allowed cases, so we can better start from there.
The check whether a certain period is allowed (non-overlapping) is :

(p2.till < p1.from)||(p1.till < p2.from)

To get the opposite, namely to check whether a certain period is in overlap, we simply negate the expression to :

!((p2.till < p1.from)||(p1.till < p2.from))

This expression can be translated to :

(p2.till >= p1.from) && (p1.till >= p2.from)

As you can see, this exactly matches the overlap cases in the figure.
Finally, the old boolean logic from college is paying off !


Post a Comment

<< Home