Ensure no collisions between multiple DateTimes

.NET
1

So this is one of those…What’s the most efficient method… threads.

Assume I have an array of objects, defined to have a Start and End time (as DateTimes). The array can be of any size greater than 1. If it matters, I can guarantee that the Start and End Times all fall within the same calendar month, give-or-take 4 hours on the end, and no object spans a period longer than 12 hours.

What’s the most efficient mechanism to ensure that no two objects in the array collide (overlap) in Time?

A simple staggered walk of the array? (a Selection Sort, effectively)

Note: I dont care about how many/which, a simple boolean true-false of whether or not there is at least one collision in the set.

2

My favorite kind of problem :slight_smile:

I once wrote a calendar/scheduling program that had to ensure no overlaps of scheduled events. Events were defined to start and end on 15-minute boundaries. What I did was put all the events’ start and end times into a long bit array and create a big mask. Then I could easily compare a requested time slot to that bit mask to see if the time slot was already taken. Dunno if that kind of scheme is workable (depends on the resolution of your DateTimes), but it was O(n).

I presume you’ve already rejected doing a usort on the array then just running through the list comparing the end of element i to the start of element i+1.

3

It feels a bit inefficient to sort the entire array just to then walk it a second time? I’m not entirely sure. O(n log(n)) + O(n)? (Given that N will be sufficiently small, likely on the scale of no bigger than 20)

4

Yeah, it does. What about just looping through:

for i=0-18
    for j=i+1 -19
        if a[i] collides with a[j] return false

return true

For just 20 elements, you’d probably spend more cycles doing various sorting things and fiddling with memory to make it fancy.

6

Yeah, thats what I had settled on in the first place, the ‘staggered loop’… (The code isn’t in a function that i want to return from at this point, so i had to ‘break’ from the loops)…

bool iscollided = false;
for (x = 0; x < a.length; x++) {
  for(y = x+1; y < a.length; y++) {
     if(a[x].startDate < a[y].endDate && a[y].startDate < a[x].endDate) {
        y = a.length;
        x = a.length;
        iscollided = true;
     }
  }
}

My instinct is just always that a nested loop is suspicious for complexity, but i cant… think of a more efficient mechanism.

2 Likes
7

Not that I tested it, but I do think your first loop should go to a.length-1 rather than a.length

1 Like
8

Dont think it would technically matter in this case, because the Y loop would simply not run on the last x loop (if x = length - 1, the y loop would initialize to y = length, and immediately abort), but good catch.