Find all non-overlapping intervals within another interval

Question

I've got an array of intervals, and another interval defined as the range. The goal would be to create an array of arrays containing start and end numbers of all the intervals that do NOT overlap BUT are within the defined range.

The original use for this is that I have a server serving hundreds of thousands objects that have timestamps one second apart from each other. A request can be made with any two timestamps, so I need to store the queried objects from the server and the next time when a request is made with two different timestamps, query only the missing objects. This question uses small numbers to simplify things.

Inputs:

const intervals = [
  [3, 5],
  [7, 9],
];

const range = [2, 11];

The output in this case would be [[2, 3], [5, 7], [9, 11]]

The intervals are always sorted by the start date and there are never overlaps in the input intervals, because the merging and sorting is done prior, per this answer https://stackoverflow.com/a/67717721/13585195

I've managed to come up with a solution for this specific case, but the problem arises when trying to cover other cases, e.g.:

1. Input: Intervals: [[3, 5]]; Range: [4, 8]; Output: [[5, 8]]
2. Input: Intervals: [[7, 11]]; Range: [2, 8]; Output: [[2, 7]]
3. Input: Intervals: [[3, 5], [6, 8]]; Range: [4, 7]; Output: [[5, 6]]
4. Input: Intervals: [[5, 10], [15, 20], [25, 30]]; Range: [0, 35]; Output: [[0, 5], [10, 15], [20, 25], [30, 35]]

The code I have for now checks if the wanted range is already in the cache and if it overlaps partially with the cached dates:

  const partiallyCached = cachedDates.some(
    (cachedDate) =>
      range.start.getTime() <= cachedDate.end.getTime() &&
      cachedDate.start.getTime() <= range.end.getTime()
  );

  if (partiallyCached) {
    console.log("Partially cached, merging query");

    const queryRange = functionToFindNonOverlappingIntervalsInRange(cachedDates, range);

    const newCachedDates = mergeOverlappingDateRanges([...cachedDates, range]);

    return {
      cache: newCachedDates,
      queryRange,
    };
  }

I'm also wondering if I should just keep writing if statements to narrow down each case as written above and write a separate function for each case or if it's possible to write a single function that solves all the cases.

Answer 1

You could take the start value of range and check the intervals and build a new array.

const
    getInbetween = (intervals, range) => {
        const
            result = [];
            
        let value = range[0],
            index = 0;

        while (value < range[1] && index < intervals.length) {
            let [left, right] = intervals[index];
            if (value < left) result.push([value, left]);
            value = right;
            index++;
        }
        if (value < range[1]) result.push([value, range[1]]);
        return result;
    };

console.log(getInbetween([[3, 5], [7, 9]], [2, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 8]));

.as-console-wrapper { max-height: 100% !important; top: 0; }