@historydev

Каким алгоритмом воспользоваться для поиска вхождений диапазона чисел в другой диапазон?

Есть очередь любого формата, первое что пришло в голову объекты, но скорее всего будет что-то вроде [[0, 1], [50, 60]], в ней хранятся N диапазонов.
Необходимо сравнить в порядке первый пришёл - первый ушёл диапазоны в этой очереди и вернуть два совпавших диапазона.

Если a входит в d - вернуть [a, d], если b входит в a - вернуть [b, a]

Очень важна производительность, скорее всего есть какой-то алгоритм, но я в них не силён.

const a = [25, 40];
const b = [18, 18];
const c = [18, 60];
const d = [19, 47];
const rangeQueue = [
  {
    id: 0,
    range: a
  },
  {
    id: 1,
    range: b
  },
  {
    id: 2,
    range: c
  },
  {
    id: 3,
    range: d
  },
];

const selectRange = (rangesArr) => {
	/* answer */
	return [rangesArr[0], rangesArr[1]];
}

console.log(selectRange(rangeQueue));


  • Вопрос задан
  • 198 просмотров
Решения вопроса 1
@KarlJohnson
Задачу не совсем понял. Но вот как понял
const testArray = [[25, 40], [18, 18], [18, 60], [19, 47]];

for (let i = 0; i < testArray.length; i++) {
    for (let j = 0; j < testArray.length; j++) {
        if (i === j)
            continue;
        if (testArray[i][0] >= testArray[j][0] && testArray[i][1] <= testArray[j][1])
            console.log(`[[${testArray[i]}], [${testArray[j]}]]`);
    }
}


Ответ:
[[25,40], [18,60]]
[[25,40], [19,47]]
[[18,18], [18,60]]
[[19,47], [18,60]]
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Самое быстрое решение - с использованием двумерных структур данных, вроде двумерного дерева отрезков.

Вы каждый отрезок представляете в виде точки на плоскости. Когда приходит новая точка, вам надо в квадрантах относительно нее (левый верхний и правый нижний) найти минимальный номер точки. При нахождени , она удаляется из мтруктуры данных и вы нашли ей пару. Иначе добаляйте новую точку в структуру данных.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
function createQueue(onMatch) {
    const queue = [];

    const checkItem = (item, range, i) => {
        if (item[0] <= range[0] && range[1] <= item[1]) {
            queue.splice(i, 1);
            onMatch(range, item);
            return true;
        }
        return false;
    };
    
    const add = (range) => {
        for (let i = 0; i < queue.length; ++i) {
            if (checkItem(queue[i], range, i) || checkItem(range, queue[i], i)) {
                return;
            }
        }
        queue.push(range);
    };

    return {queue, add};
}

// пример использования
const q = createQueue((a, b) => console.log(a, b));

q.add([2, 4]);
q.add([3, 5]);
q.add([4, 4]); // log ([4, 4], [2, 4])
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
SummerWeb Ярославль
от 120 000 до 180 000 ₽
КРАФТТЕК Санкт-Петербург
от 60 000 до 80 000 ₽
Brightdata Тель-Авив
от 5 500 до 6 500 $
19 июн. 2024, в 06:58
15000 руб./за проект
19 июн. 2024, в 01:11
7000 руб./за проект
18 июн. 2024, в 23:10
15000 руб./за проект