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.:
[[3, 5]];
Range: [4, 8];
Output: [[5, 8]][[7, 11]]; Range: [2, 8]; Output: [[2, 7]][[3, 5], [6, 8]]; Range: [4, 7]; Output: [[5, 6]][[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.
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; }With the assumption that this is sorted, and all intervals are merged, there are just a few situations to consider.
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]));