I am trying to come up with an efficient algorithm to do the following, ideally in javascript or golang:

Given a set of busy time intervals (start timestamp end timestamp in ms), validate an incoming timeslot to be scheduled. Assume there aren't any existing overlaps.

Example:

const timeslots = [
  { start: 10, end: 14 },
  { start: 17, end: 21 },
  { start: 30, end: 37 },
  // ...
];
const ts = timeslots.sort((a, b) => {
  return a.start - b.start;
});

const checkValid = (inc) => {
  // validation here
};

console.log(checkValid({ start: 15, end: 16 })); // should be true
console.log(checkValid({ start: 15, end: 18 })); // should be false
console.log(checkValid({ start: 16, end: 27 })); // should be false
console.log(checkValid({ start: 8, end: 39 })); // should be false

And any other edge cases not described should work as well.

CodePudding user response：

If the intervals are (1) non-overlapping and (2) sorted then you can perform a binary search to find the first one that lies just after the desired interval, and then simply check if the previous one overlaps with it. This would be O(logN) instead of O(N).

Example in Go:

package main

import (
    "fmt"
    "sort"
)

type Slot struct {
    start int
    end   int
}

var timeslots = []Slot{
    {start: 10, end: 14},
    {start: 17, end: 21},
    {start: 30, end: 37},
}

func checkValid(slot Slot) bool {
    i := sort.Search(len(timeslots), func(i int) bool {
        return timeslots[i].start > slot.end
    })
    return i == 0 || timeslots[i-1].end < slot.start
}

func main() {
    sort.Slice(timeslots, func(a, b int) bool {
        return timeslots[a].start < timeslots[b].start
    })

    fmt.Println(checkValid(Slot{start: 15, end: 16})) // should be true
    fmt.Println(checkValid(Slot{start: 15, end: 18})) // should be false
    fmt.Println(checkValid(Slot{start: 16, end: 27})) // should be false
    fmt.Println(checkValid(Slot{start: 8, end: 39}))  // should be false

}

CodePudding user response：

validate(start, end)
for timeslot in timeslots
    if start >= timeslot["start"] and start <= timeslot["end"]
        return false
    if start < timeslot["start"] and end >= timeslot["start"]
        return false
    if end >= timeslot["start"] and end <= timeslot["end"]
        return false
return true

I think something like this should work.