Алгоритмы расчета пересекающихся интервалов.

computeIntervalIntersectionsProgressive.ts

/*
* Ну и скомбинировав два этих способа, я пришел к выводу, что можно все же вычислить индексы пересечений, и при этом оставить
* простой алгоритм, не зависящий от размера числа.
* Здесь создаем объект, в который поместим индексы которые пересеклись, и точки. Да точек тут будет меньше, только 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;
    }

findIntervalsIntersections.ts

/*
* Примеры интервалов: [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]));

isIntervalsIntersect.ts

/*
* В случае, когда просто нужно знать пересекаются интервалы или нет, тут алгоритм проще.
* Для начала нам необходимо отсортировать интервалы, чтобы они шли по порядку, своей стартовой точки
* т.е. [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;
    }