5

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

Bolshoi Booze
  • 466
  • 8
  • 22
  • How do you store that time range in the database? Can you show your model? – GwynBleidD Mar 06 '19 at 13:29
  • 1
    Are t1 and t2 in your example supposed to overlap or not? It’s impossible to say if you don’t have a date attached. – dirkgroten Mar 06 '19 at 13:46
  • @dirkgroten I saw multiple algos that check overlapping times, but in my case i have two ranges that time overlap with one another. – Bolshoi Booze Mar 06 '19 at 13:50
  • 2
    what I’m saying is t1 and t2 are not overlapping if the from time is assumed to be on the same date. How could any algorithm know that the from time of t2 is supposed to be a day later than the from time of t1??? – dirkgroten Mar 06 '19 at 13:52
  • So the only way is to convert to datetime using some additional information you have in your business logic and then check for overlap – dirkgroten Mar 06 '19 at 13:55

2 Answers2

11

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.
GwynBleidD
  • 20,081
  • 5
  • 46
  • 77
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.

kellycup8
  • 121
  • 1
  • 3