Tengo una matriz de intervalos y otro intervalo definido como rango. El objetivo sería crear una matriz de matrices que contengan los números de inicio y final de todos los intervalos que NO se superponen PERO están dentro del rango definido.
El uso original de esto es que tengo un servidor que atiende a cientos de miles de objetos que tienen marcas de tiempo con un segundo de diferencia entre sí. Se puede realizar una solicitud con dos marcas de tiempo cualesquiera, por lo que debo almacenar los objetos consultados del servidor y la próxima vez que se realice una solicitud con dos marcas de tiempo diferentes, consultar solo los objetos que faltan. Esta pregunta usa números pequeños para simplificar las cosas.
Entradas:
const intervals = [ [3, 5], [7, 9], ]; const range = [2, 11]; La salida en este caso sería [[2, 3], [5, 7], [9, 11]]
Los intervalos siempre se ordenan por la fecha de inicio y nunca hay superposiciones en los intervalos de entrada, porque la combinación y la clasificación se realizan antes, según esta respuesta https://stackoverflow.com/a/67717721/13585195
Logré encontrar una solución para este caso específico, pero el problema surge al tratar de cubrir otros casos, por ejemplo:
[[3, 5]]; Rango: [4, 8]; Salida: [[5, 8]][[7, 11]]; Rango: [2, 8]; Salida: [[2, 7]][[3, 5], [6, 8]]; Rango: [4, 7]; Salida: [[5, 6]][[5, 10], [15, 20], [25, 30]]; Rango: [0, 35]; Salida: [[0, 5], [10, 15], [20, 25], [30, 35]]El código que tengo por ahora verifica si el rango deseado ya está en el caché y si se superpone parcialmente con las fechas almacenadas en caché:
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, }; } También me pregunto si debo seguir escribiendo declaraciones if para reducir cada caso como se escribió anteriormente y escribir una función separada para cada caso o si es posible escribir una sola función que resuelva todos los casos.
Puede tomar el valor inicial del rango y verificar los intervalos y construir una nueva matriz.
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; }Con la suposición de que esto está ordenado y todos los intervalos están fusionados, solo hay algunas situaciones a considerar.
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]));