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.

CodePudding user response：

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; }

CodePudding user response：

With the assumption that this is sorted, and all intervals are merged, there are just a few situations to consider.

1. The start of the range precedes the first element.
2. The start of the range intersects the first element.
3. The end of the range intersects the last element.
4. The end of the range exceeds the last element.
5. An element lays within the start and stop of the range.

function getNonOverlappingIntervals(intervals, [rangeStart, rangeStop]) {
    const output = [];
    let prevStop = null;

    const intervalsInRange = intervals.filter(([start, stop]) => {
        if (rangeStart <= start && rangeStop >= stop) return true;
        if (start < rangeStart && stop > rangeStart) return true;
        if (start < rangeStop && stop > rangeStop) return true;
        return false;
    });

    // check if rangeStart precedes first interval
    if (intervalsInRange[0][0] > rangeStart) {
        output.push([rangeStart, intervalsInRange[0][0]]);
        prevStop = intervalsInRange[0][1];
    } else if (intervalsInRange[0][0] < rangeStart) {
        prevStop = intervalsInRange[0][1];
    }

    // iterate intervals and compare against last checked interval
    if (intervalsInRange.length > 2) {
        for (let i = 1; i < intervalsInRange.length; i  ) {
            output.push([prevStop, intervalsInRange[i][0]]);
            prevStop = intervalsInRange[i][1];
        }
    }

    // check if rangeStop exceeds last interval
    if (intervalsInRange[intervalsInRange.length - 1][1] < rangeStop) {
        output.push([intervalsInRange.at(-1)[1], rangeStop]);
    }

    return output;
}

console.log(getNonOverlappingIntervals([[3, 5],[7, 9]], [2, 11]));
console.log(getNonOverlappingIntervals([[3, 5]], [4, 8]));
console.log(getNonOverlappingIntervals([[7, 11]], [2, 8]));
console.log(getNonOverlappingIntervals([[3, 5], [6, 8]], [4, 7]));
console.log(getNonOverlappingIntervals([[5, 10], [15, 20], [25, 30]], [0, 35]));