Last active
February 18, 2024 20:41
-
-
Save dastanaron/0f49b96ca6d03251506beb3a4e32db22 to your computer and use it in GitHub Desktop.
Алгоритмы расчета пересекающихся интервалов.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Ну и скомбинировав два этих способа, я пришел к выводу, что можно все же вычислить индексы пересечений, и при этом оставить | |
* простой алгоритм, не зависящий от размера числа. | |
* Здесь создаем объект, в который поместим индексы которые пересеклись, и точки. Да точек тут будет меньше, только 2, | |
* чтобы показать в каких точках произошло пересечение, всю глубину, как в 1ом алгоритме мы не выявим. | |
* По сути поиск как во втором алгоритме, только мы клонировали массив, чтобы нам можно было искать индексы в изначальной структуре. | |
* Для этого мы заводим вот такую функцию findIndexByNumber, она то и будет по числу возвращать нам индекс. | |
* | |
* Есть и в этом алгоритме недостаток, если в передаваемых диапазонах, встретятся одинаковые числа, | |
* то индекс для обоих случаев проставится одинаковый | |
*/ | |
interface IntersectionInterval { | |
indexes: number[], | |
intersections: number[], | |
} | |
function computeIntervalIntersectionsProgressive(...intervals: number[][]): IntersectionInterval[] | |
{ | |
const clonedIntervals = intervals.slice(); | |
const sortedIntervals = clonedIntervals.sort((a, b) => { | |
if (a[0] < b[0]) { | |
return -1; | |
} | |
if (a[0] > b[0]) { | |
return 1; | |
} | |
return 0; | |
}); | |
const intersections: IntersectionInterval[] = []; | |
let lastInterval: number[] = []; | |
const findIndexByNumber = (val: number) => { | |
for (const index in intervals) { | |
if (val === intervals[index][0] || val === intervals[index][1]) { | |
return Number(index); | |
} | |
} | |
return -1; | |
}; | |
for (const index in sortedIntervals) { | |
const interval = sortedIntervals[index]; | |
if (Number(index) === 0) { | |
lastInterval = interval; | |
continue; | |
} | |
if (interval[0] <= lastInterval[1]) { | |
intersections.push({ | |
indexes: [findIndexByNumber(interval[0]), findIndexByNumber(lastInterval[1])], | |
intersections: [interval[0], lastInterval[1]] | |
}) | |
} | |
lastInterval = interval; | |
} | |
return intersections; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Примеры интервалов: [1, 10], [11, 20], [5, 15] | |
* Если мы нарисуем их, то получим очевидную картину, что 3й интервал пересекает и 1 и второй в точках [5, 10] и [11, 15] | |
* Я долго думал, как это высчитывать для неопределенного количества интервалов. И решил пойти через Анализ. | |
* NB1. По анализу [1, 10] это 1 <= x <= 10; т.е. x Это массив чисел от 1, до 10 [1,2,3,4,5,6,7,8,9,10], поэтому просто берем интервал | |
* и заполняем X от минимума до максимума. | |
* NB2. Далее мы понимаем, что в пересекающихся интервалах, часть массива значений x будет пересекаться, и чтобы | |
* вычислить все возможные перечисления, мы идем в два цикла, один от 0, другой от максимума, для того, | |
* чтобы не пропустить ни одного массива с найденными X и сравнить друг с другом | |
* NB3. Однако мы сталкиваемся с проблеммой в таком цикле, он начинает сравнивать индексы например [0, 0] или [0, 1] [1, 0] | |
* а ведь нам подрядок сравнения не важен, главное, чтобы все друг с другом посравнивались, и если уже сравнили 0 индекс с 1, | |
* то 1й с нулевым сравнивать не нужно. Для этого и сделана переменная функция isSkip, которая проверяет, | |
* сравнивали ли мы массивы с такими индексами или нет. | |
* | |
* Крупный недостаток этого алгоритма в том, что при заполнении x среди интервалов с большими числами, | |
* может сохрать всю память под массив и естесвенно обвалиться. Это прямо существенный недостаток, поэтому алгоритм подходит, | |
* только для небольших интервалов. | |
*/ | |
function computeIntervalIntersections(...intervals: number[][]): number[][] | |
{ | |
const foundedX: number[][] = []; | |
for (const index in intervals) { | |
const interval = intervals[index]; | |
if (interval.length !== 2 && interval[0] > interval[1]) { | |
throw new Error('Invalid interval'); | |
} | |
foundedX[index] = []; | |
// see NB1. | |
for (let i = interval[0]; i <= interval[1]; i++) { | |
foundedX[index].push(i) | |
} | |
} | |
const intersections: number[][] = []; | |
const excludedIndexes: number[][] = []; | |
// see NB3 | |
const isSkip = (index: number, revertIndex: number) => { | |
for (const excludeElement of excludedIndexes) { | |
if (excludeElement.includes(index) && excludeElement.includes(revertIndex)) { | |
return true; | |
} | |
} | |
return false; | |
}; | |
//see NB2 | |
for (let index = 0; index < foundedX.length; index++) { | |
for (let revertIndex = foundedX.length - 1; revertIndex >= 0; revertIndex--) { | |
//see NB3 | |
if (index !== revertIndex && !isSkip(index, revertIndex)) { | |
excludedIndexes.push([revertIndex, index]); | |
intersections.push(arrayIntersect(foundedX[index], foundedX[revertIndex])); | |
} | |
} | |
} | |
return intersections; | |
} | |
function arrayIntersect(arr1: number[], arr2: number[]): number[] { | |
return arr1.filter((e) => { | |
return arr2.includes(e); | |
}); | |
} | |
console.log(computeIntervalIntersections([1,10], [11, 20], [5, 15])); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* В случае, когда просто нужно знать пересекаются интервалы или нет, тут алгоритм проще. | |
* Для начала нам необходимо отсортировать интервалы, чтобы они шли по порядку, своей стартовой точки | |
* т.е. [1, 10], [11, 20], [5, 15] превратить в [1, 10], [5, 15], [11, 20]. | |
* Теперь, когда массивы интервалов отсортированы, мы можем просто в одном цикле сравнивать, чтобы граница | |
* начала следующего интервала была больше предыдущей, тогда они не пересекаются. | |
* Однако, нам удобнее искать пересекающиеся интервалы, поэтому выворачиваем условие, если граница текущего интервала | |
* в цикле, меньше или равна концу предыдущего интервала, значит точно есть пересечение, кидаем return true тем самым | |
* обрываем цикл, и выбрасываем ответ, что мы нашли пересечение. | |
* | |
* Плюс этого алгоритма в простоте, и он не зависит от размера числа в отличии от предыдущего, но и доработать его под то, | |
* чтобы можно было точно найти пересечения, и указать между какими индексами | |
*/ | |
function isIntervalIntersection(...intervals: number[][]): boolean | |
{ | |
const sortedIntervals = intervals.sort((a, b) => { | |
if (a[0] < b[0]) { | |
return -1; | |
} | |
if (a[0] > b[0]) { | |
return 1; | |
} | |
return 0; | |
}); | |
let lastInterval: number[] = []; | |
for (const index in sortedIntervals) { | |
const interval = sortedIntervals[index]; | |
if (Number(index) === 0) { | |
lastInterval = interval; | |
continue; | |
} | |
if (interval[0] <= lastInterval[1]) { | |
return true; | |
} | |
lastInterval = interval; | |
} | |
return false; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment