Checking if two 'time ranges' overlap with one another

Question

I have an object saved in db with time range (t1): 11:45-00:15. Now I have another time range from request : (t2) 00:05-00:10. What is most optimal way to find whether this new time range t2 overlaps with an already saved object with time ranges t1. This is the case of midnight, that is where the day is changing. For same day, i'm successfully able to find overlapping time ranges. I don't have a datetime field, rather i have time field only, hence i have to made do with what i already have.

In models t1 will be stored as:

start_time = TimeField(null=True, blank=True, db_index=True)
end_time = TimeField(null=True, blank=True, db_index=True)

so 11:45 will be stored in start_time and 00:15 will be stored in end_time

Answer 1

I'm assuming that in cases when start_time is bigger than end_time, time range should just overlap, as the time was cyclic and we just don't care about date (in other words, those ranges represents events that are happening every day and we want to detect if any event overlaps with any other event)

With this assumption, here is quick answer:

if t2.start_time > t2.end_time:
    condition = (
        Q(start_time__gt=F('end_time')) |
        Q(start_time__lt=t2.end_time) |
        Q(end_time__gt=t2.start_time)
    )
else:
    condition = (
        Q(start_time__gt=F('end_time'), start_time__lt=t2.end_time) |
        Q(start_time__gt=F('end_time'), end_time__gt=t2.start_time) |
        Q(start_time__lt=t2.end_time, end_time__gt=t2.start_time)
    )

Explanation

There are 24 cases of arranging start times and end times of each event (excluding cases when any two dates are equal). From those 24 cases, 20 of them mean that there is an overlap and 4 of them mean that there is no overlap. As no overlap contains far less cases, lets look closer at it, so here are those 4 cases :

1. t1.end_time < t2.start_time < t2.end_time < t1.start_time
2. t1.start_time < t1.end_time < t2.start_time < t2.end_time
3. t2.start_time < t2.end_time < t1.start_time < t1.end_time
4. t2.end_time < t1.start_time < t1.end_time < t2.start_time

You can represent those cases in python code as follows (redundant whitespaces added to show how we can group them):

(                                t1.start_time > t2.end_time and t2.start_time > t1.end_time and t2.start_time < t2.end_time) or \ # 1.
(t1.start_time < t1.end_time                                 and t2.start_time > t1.end_time and t2.start_time < t2.end_time) or \ # 2.
(t1.start_time < t1.end_time and t1.start_time > t2.end_time                                 and t2.start_time < t2.end_time) or \ # 3.
(t1.start_time < t1.end_time and t1.start_time > t2.end_time and t2.start_time > t1.end_time                                )      # 4. 

As we can see, it can be simplified to tell that items are not overlapping if any 3 of those 4 conditions apply:

(
    t1.start_time < t1.end_time,
    t1.start_time > t2.end_time,
    t2.start_time > t1.end_time,
    t2.start_time < t2.end_time,
)

If we want to find out if 2 items are overlapping, we have to reverse this condition. So items are overlapping if any of 2 of those 4 conditions apply:

(
    t1.start_time > t1.end_time,
    t1.start_time < t2.end_time,
    t2.start_time < t1.end_time,
    t2.start_time > t2.end_time,
)

so full condition looks like:

t1.start_time > t1.end_time and t1.start_time < t2.end_time or \
t1.start_time > t1.end_time and t2.start_time < t1.end_time or \
t1.start_time > t1.end_time and t2.start_time > t2.end_time or \
t1.start_time < t2.end_time and t2.start_time < t1.end_time or \
t1.start_time < t2.end_time and t2.start_time > t2.end_time or \
t2.start_time < t1.end_time and t2.start_time > t2.end_time

Dressing it in django queryset, as we have 1 condition that we can check before executing it (we can check if start_time of t2 is lower than end_time of t2), we can divide it into 2 cases and simplify both of them.

if t2.start_time > t2.end_time:
    condition = (
        Q(start_time__gt=F('end_time')) |
        Q(start_time__lt=t2.end_time) |
        Q(end_time__gt=t2.start_time)
    )
else:
    condition = (
        Q(start_time__gt=F('end_time'), start_time__lt=t2.end_time) |
        Q(start_time__gt=F('end_time'), end_time__gt=t2.start_time) |
        Q(start_time__lt=t2.end_time, end_time__gt=t2.start_time)
    )

But what about equals?

Yes... We've skipped that... There are 3 decisions that we need to make to include them.

1. Can any range have 0 length (start and end equal) and not collide with anything?
2. Can any range have 24h length (start and end equal) and collide with everything?
3. If start of one range is equal to end of another range, are they overlapping?

1st and second condition cannot be both yes. If you answered for all of those questions "no", then you're done, code shown above will work in your case. If you answered yes for any question, apply corresponding modification from list below:

1. Add .exclude(start_time=F('end_time')) to the final queryset and assume that t2 is not overlapping with anything else if t2.start_time == t2.end_time and just skip the check
2. Add | Q(start_time=F('end_time') to both conditions and assume that t2 is overlapping with everything else if t2.start_time == t2.end_time and just skip the check
3. Replace every __gt with __gte and every __lt with __lte in both conditions, when there is t2 in right side of inner condition instead of F function.

Answer 2

This logic should do it:

if (d1.start_time < d2.start_time < d1.end_time) or (d1.start_time < d2.end_time < d1.end_time) or (d2.start_time <= d1.start_time and d2.end_time >= d1.end_time): return True

Explanation:

First, check if the start and end times for d2 overlap w d1's time range. If it does, return True.

Next, see if d2 is either larger or the same as d1. If it is, return True.

Otherwise, these dates do not overlap.