most efficient reservation overlap detection in javascript

Question

I have an array of rooms

Each room can have many reservations

Reservations have a start and end time.

I can detect if a reservation overlaps another reservation with

res1Start < res2End && res1End > res2Start === overlap

I am trying trying to take the reservations, decide which over lap which, take into account multiple reservations overlapping multiple other reservations and then stack them in a diagram. like this

my current method does not account for every scenario.

One being two reservations that overlap each other and overlap the exact same other reservations.

3 overlapping reservations looking good

4th one added that straddles the same reservations as the top one and also overlaps the top one

You can see that the 4th one gets one extra unit of margin from the top added then is necessary.

also if the new overlapping reservation should overlap without increasing the 'depth' of the row the depth is still increased

My question is what is the most efficient way to iterate through each room -> iterate through each reservation in that room -> compare it to each other reservation in that room only once and keep record of how many overlaps in each room

The result I am looking for is a variable for each reservation that tells me how tall it should be relative to its containing row (reservation that overlaps 2 others should be a third the height of the row) and a variable for each reservation telling me how much distance from the top of the row to the top of the reservation should be so that it has its own space on the row

each step of the solution should be possible with javascript

+25 rep for a scalable solution.

+50 rep for a full explanation of the techniques / patterns used to come to the solution.

Update: thanks you for the advice the 'greedy' solution works great for getting the tasks into the correct 'track' and if you are not concerned with the height of your row increasing then this method is all you would need. however in a gantt situation were there could be multiple overlaps the gantts row could become unreasonably high. To combat this I need to adjust the height of each task relative to how many other tasks it overlaps.

this can be done with the 'greedy' solution fairly easily, everytime there is a conflict decrease both tasks heights. the scenario that this does not cover is the following

All the tasks are placed correctly but the task on the far left is not aware that the task it overlaps overlaps with a number of other tasks so it does not decrease its height enough. the task on the top right gets placed without knowing there is an overlapping task in 'track' 2 below it so it misses out on one height decrease and visually overlaps the task below it.

Is there a way to make each task aware of each of its overlaps' overlaps without a second pass over the data?

Answer 1

If I understand your problem correctly, here is a simple greedy scheduler that ought to work fine. With careful implementation it will be O(n log n + log t) for n reservations and t tracks required in the schedule.

Compute an array of "events" that are records of the form:

{ 
  time: [ contains the event time ]
  reservation: [ points to a reservation ]
}

I am assuming a reservation looks like this:

{
  room: [ reference to a room record ]
  start: [ start time of the reservation ]
  end: [ end time of the reservation ]
  track: [ initially null; set to 0... to show 
           vertical location of reservation in diagram ]
}

The events array contains two records for each reservation: one for its start time and one for the end. Note that you can determine the kind of an event - start or end - after it's created by comparing its time field with its reservation.start. If they match, it's a start event, else an end event.

After the array is created, this algorithm will greedily assign reservations to tracks:

Sort the event array A on a key of time ascending
Let T be an array indexed by "track" in the output graphic of lists of reservations.
Let B be an array of booleans, also indexed by "track", initially with 0 elements.
for each event E in A
  if E is a start event
    Search B for the index I of a "false" entry
    if I is not found
      Append new a new element onto the end of each of B and T
      Set I to be the index of these new elements
    end
    Add E.reservation to the tail of T[I]
    Set E.reservation.track = I
    Set B[I] = true
  else // E is an end event
    Let I = E.reservation.track
    Set B[I] = false
  end

When this finishes running, all the reservations can be drawn in the diagram using their start, end, and track fields.

You can control the appearance of the diagram with different choices of the search in this line:

 Search B for the index I of a "false" entry

I believe you want "best fit." This means find the false entry of the track I where the end time of the last reservation in list T[I] is closest to E.time. You may come up with other heuristics you like better.

Answer 2

Is there a way to make each task aware of each of its overlaps without a second pass over the data?

The code below is O(N^2), so it's probably not an optimal solution but I'm posting it anyway in case it's helpful. It uses a nested loop for every reservation combination to count the # of overlaps and to assign tracks greedily.

//pre-processing:
//group reservations & sort grouped reservations by starting time

var groupedReservations = [
    {id:2,start:1,end:2,overlap_count:0,track:0},
    {id:3,start:2,end:3,overlap_count:0,track:0},
    {id:4,start:2,end:4,overlap_count:0,track:0},
    {id:5,start:2,end:6,overlap_count:0,track:0},    
    {id:6,start:3,end:8,overlap_count:0,track:0},
    {id:7,start:6,end:9,overlap_count:0,track:0},    
];

countOverlaps(groupedReservations);
console.log(groupedReservations);

//populates overlap & track properties
function countOverlaps(reservations) {

    var len = reservations.length;

    //check overlap for reservation combination
    for(var i=0; i<len; i++) {            
        for(var j=i+1; j<len; j++) {
            if(reservations[i].end > reservations[j].start) {
                //if there's an overlap increase the counters on both reservations
                reservations[i].overlap_count++;
                reservations[j].overlap_count++;
                //if there's an overlap on the same track
                //then change the inner reservation's track
                if(reservations[j].track == reservations[i].track)
                    reservations[j].track++;                    
            }
            else break; 
            // break once a non-overlapping reservation is encountered
            // because the array is sorted everything afterwards will also be
            // non-overlapping           
        }
    }    
}

To keep track of the overlaps of overlaps, instead of storing the count, you can store a reference to the overlapped reservations in an array which will let you get the overlaps of overlaps (as deep as needed). The overlap count can be retrieved by getting the overlap array's length.

//pre-processing:
//group reservations & sort grouped reservations by starting time

var groupedReservations = [
    {id:2,start:1,end:2,overlap:[],track:0},
    {id:3,start:2,end:3,overlap:[],track:0},
    {id:4,start:2,end:4,overlap:[],track:0},
    {id:5,start:2,end:6,overlap:[],track:0},    
    {id:6,start:3,end:8,overlap:[],track:0},
    {id:7,start:6,end:9,overlap:[],track:0},    
];

countOverlaps(groupedReservations);
console.log(groupedReservations);

//populates overlap & track properties
function countOverlaps(reservations) {

    var len = reservations.length;

    //check overlap for reservation combination
    for(var i=0; i<len; i++) {            
        for(var j=i+1; j<len; j++) {
            if(reservations[i].end > reservations[j].start) {
                //if there's an overlap, store a reference to the overlap
                reservations[i].overlap.push(reservations[j]);
                reservations[j].overlap.push(reservations[i]);
                //if there's an overlap on the same track
                //then change the inner reservation's track
                if(reservations[j].track == reservations[i].track)
                    reservations[j].track++;                    
            }
            else break; 
            // break once a non-overlapping reservation is encountered
            // because the array is sorted everything afterwards will also be
            // non-overlapping           
        }
    }    
}

Answer 3

As Gene said, it is not so complicated with events.

note: This is similar to event sourcing.

calendar-test.js

define(["calendar"], function (Calendar) {

    /*
     *       | 09 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 |
     *       |         A    A    B    B    C    C    G    |
     *       |              D    D    D    D    F         |
     *       |    E    E    E                             |
     * */

    var noon = new Date("2014-07-01T12:00:00Z").getTime();
    var hour = 60 * 60 * 1000;

    var reservations = [
        {
            label: "A",
            start: new Date(noon - 2 * hour),
            end: new Date(noon)
        },
        {
            label: "B",
            start: new Date(noon),
            end: new Date(noon + 2 * hour)
        },
        {
            label: "C",
            start: new Date(noon + 2 * hour),
            end: new Date(noon + 4 * hour)
        },
        {
            label: "D",
            start: new Date(noon - hour),
            end: new Date(noon + 3 * hour)
        },
        {
            label: "E",
            start: new Date(noon - 3 * hour),
            end: new Date(noon)
        },
        {
            label: "F",
            start: new Date(noon + 3 * hour),
            end: new Date(noon + 4 * hour)
        },
        {
            label: "G",
            start: new Date(noon + 4 * hour),
            end: new Date(noon + 5 * hour)
        }
    ];

    var calendar = new Calendar(reservations);

    describe("a simple calendar", function () {

        it("which has 7 reservations", function () {
            expect(calendar.getReservations().length).toEqual(7);
        });

        it("and 6 overlaps: AD,AE,DE,BD,CD,CF", function () {
            expect(calendar.getOverlaps().length).toEqual(6);
            var overlapLabels = [];
            calendar.getOverlaps().forEach(function (overlap) {
                var overlapLabel;
                reservationLabels = [
                    overlap[0].getLabel(),
                    overlap[1].getLabel()
                ];
                reservationLabels.sort();
                overlapLabel = reservationLabels.join("");
                overlapLabels.push(overlapLabel);
            });
            overlapLabels.sort();
            expect(overlapLabels.join(",")).toEqual("AD,AE,BD,CD,CF,DE");
        });

    });

});

calendar.js

define(function () {

    var Calendar = function (options) {
        this.reservations = options;
        this.overlapFinder = new OverlapFinder();
    };

    Calendar.prototype = {
        constructor: Calendar,
        getReservations: function () {
            return this.reservations;
        },
        getOverlaps: function () {
            return this.overlapFinder.getOverlaps(this.reservations);
        }
    };


    var OverlapFinder = function () {
    };

    OverlapFinder.prototype = {
        constructor: OverlapFinder,
        getOverlaps: function (reservations) {
            this.overlaps = [];
            this.openReservations = {};
            this.createEvents(reservations).forEach(function (event) {
                var reservation = event.getReservation();
                if (event instanceof ReservationStart)
                    this.startReservation(reservation);
                else {
                    this.endReservation(reservation);
                    this.extractOverlapsFromOpenReservations(reservation);
                }
            }.bind(this));
            return this.overlaps;
        },
        createEvents: function (reservations) {
            var events = [];
            reservations.forEach(function (reservation) {
                events.push(
                    new ReservationStart(reservation),
                    new ReservationEnd(reservation)
                );
            });
            events.sort(function (a, b) {
                return a.getTime() - b.getTime();
            });
            return events;
        },
        startReservation: function (reservation) {
            this.openReservations[reservation.getId()] = reservation;
        },
        endReservation: function (reservation) {
            delete(this.openReservations[reservation.getId()]);
        },
        extractOverlapsFromOpenReservations: function (reservation) {
            for (var id in this.openReservations) {
                if (!this.openReservations.hasOwnProperty(id))
                    continue;
                var openReservation = this.openReservations[id];
                if (reservation.getEndTime() > openReservation.getStartTime())
                    this.overlaps.push([reservation, openReservation]);
            }
        }
    };


    var nextReservationId = 1;

    var Reservation = function (options) {
        this.options = options;
        this.id = nextReservationId++;
    };

    Reservation.prototype = {
        constructor: Reservation,
        getId: function () {
            return this.id;
        },
        getStartTime: function () {
            return this.options.start;
        },
        getEndTime: function () {
            return this.options.end;
        },
        getLabel: function () {
            return this.options.label;
        }
    };


    var ReservationEvent = function (reservation) {
        this.reservation = reservation;
    };
    ReservationEvent.prototype = {
        constructor: ReservationEvent,
        getReservation: function () {
            return this.reservation;
        }
    };


    var ReservationStart = function (reservation) {
        ReservationEvent.apply(this, arguments);
    };
    ReservationStart.prototype = Object.create(ReservationEvent.prototype);
    ReservationStart.prototype.constructor = ReservationStart;
    ReservationStart.prototype.getTime = function () {
        return this.reservation.getStartTime();
    };


    var ReservationEnd = function (reservation) {
        ReservationEvent.apply(this, arguments);
    };
    ReservationEnd.prototype = Object.create(ReservationEvent.prototype);
    ReservationEnd.prototype.constructor = ReservationEnd;
    ReservationEnd.prototype.getTime = function () {
        return this.reservation.getEndTime();
    };


    return function (reservationOptionsList) {
        var calendarOptions = [];
        reservationOptionsList.forEach(function (reservationOptions) {
            calendarOptions.push(new Reservation(reservationOptions));
        });
        return new Calendar(calendarOptions);
    };
});