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

Question

[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));

Comments

[Wataru]

Не ясна задача. Сравниваются-то пары отрезков. Что значит в порядке "первый пришел первый ушел"? Это порядок на один отрезок. Вот у вас N отрезков. Надо найти такие i и j, что отрезок i входит в отрезок j. Но какие условия на i, j? Лексикографически минимальная пара?

Что значит "входит"? Входит ли отрезок [18, 18] в [10, 18]? Совпадающие отрезки считаются за вхождение?

[historydev]

Wataru, Значит что сначала подбирается пара самому старому элементу в очереди, т.к. нужно того кто ждёт дольше всего обслужить как можно быстрее.

Если пары ему не нашлось, переходим к следующему и т.д.

i может входить в j и наоборот, совпадающие считаются вхождением.

Не знаю что такое лексикографически минимальная пара

[Wataru]

historydev, лексикографически - в смысле сначала минимизируем i, а среди всех минимальных минимизируем j.

Можете описать, что эти отрезки-то значат? Что это за очередь?

Т.е. ищем пару i < j, т.ч. один из них входит в другой, с минимальным i, из всех таких - с минимальным j?

Вам надо будет потом эту пару из очереди удалять и опять искать пару? Что вы потом с этой парой делаете? От этого зависит, какой алгоритм самый лучший.

[historydev]

Wataru,

Т.е. ищем пару i < j, т.ч. один из них входит в другой, с минимальным i, из всех таких - с минимальным j?

Ничего не понял.

Тяжело объяснить, когда не понимаешь математику.

Да, нужно будет удалять пару.

Объясню задачу целиком:

Есть чат, в чате можно выбрать диапазон возраста, свой и собеседника.
Нужно подобрать собеседника по возрасту.

При этом нужно учесть, тот кто первый начал поиск, в случае появления подходящего по возрасту собеседника, он первый на него претендует, даже если после него десяток таких-же.

Answer 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]]

Comments

[historydev]

Я уточнил задачу в комментариях

Answer 2

[Wataru]

Самое быстрое решение - с использованием двумерных структур данных, вроде двумерного дерева отрезков.

Вы каждый отрезок представляете в виде точки на плоскости. Когда приходит новая точка, вам надо в квадрантах относительно нее (левый верхний и правый нижний) найти минимальный номер точки. При нахождени , она удаляется из мтруктуры данных и вы нашли ей пару. Иначе добаляйте новую точку в структуру данных.

Comments

[Alexandroppolus]

там интервалы возраста (целое от 0 до 120), причем для совпадения подходит как надинтервал, так и подинтервал, соответственно в очереди не будет более 120 элементов (на практике - не более 60-70), так что можно не заморачиваться и каждый раз просто обходить очередь

Answer 3

[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])