Data structure for non-overlapping ranges within a

Question

I need a data structure that can store non-overlapping ranges within a single dimension. The entire range of the dimension need not be completely covered.

An example would be a conference room scheduler. The dimension is time. No two schedules may overlap. The conference room isn't always scheduled. In other words, for a given time there can be at most one schedule.

A quick solution is for a range to store the start and end times.

Range {
    Date start
    Date end
}

This is non-normalized and requires the container to enforce no overlapping. For two adjacent ranges, the previous' end will be redundant with the next's start.

Another scheme might involve storing one boundary value with each range. But for a contiguous sequence of ranges, there will always be one more boundary values than ranges. To get around this the sequence could be represented as alternating boundary values and ranges:

B = boundary value, r = range

B-r-B-r-B

The data structure might look like:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

In essence it's a doubly linked list with alternating types.

Ultimately, whatever data structure I use will be represented in both memory (application code) and a relational database.

I'm curious what academic or industry tried solutions exists.

Answer 1

If you are lucky (!) enough to be using Postgres, you can use a tstzrange column, and apply a constraint to prevent overlaps. The bonus of using a range type is that it will inherently prevent start being greater than finish.

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =);

You may need to CREATE EXTENSION IF NOT EXISTS btree_gist, as creating a gist using && is not supported without that extension.

Answer 2

This is called the "Unary Resource" constraint in the Constraint Programming world. There is a lot of research in this area, specifically for the case when the event times aren't fixed, and you need to find time-slots for each of them. There is a commercial C++ package that does your problem and more Ilog CP, but it is likely overkill. There is also a somewhat open-source version called eclipse (no relation to the IDE).