Как найти пересечения элементов в массиве?

Question

[fillpower]

Есть 2 двумерных массива с началом и концом интервала:

[[8, 12], [17, 22]],
[[5, 11], [14, 18], [20, 23]]

Нужно найти пересечения между интервалами массивов.
Ответ: [[8, 11], [17, 18], [20, 22]]

Comments

[Василий Банников]

А вы попробовали на бумажке составить алгоритм?

[fillpower]

Василий Банников,

arr1.forEach(([arr1FirstValue, arr1SecondValue]) => {
        for (let k = 0; k < arr2.length; k++) {
            const [arr2FirstValue, arr2SecondValue] = arr2[k]
            if (arr1FirstValue < arr2FirstValue) {
                if (arr1SecondValue < arr2SecondValue) {
                    arr.push([arr2FirstValue, arr1SecondValue])
                } else {
                    arr.push([arr2FirstValue, arr1SecondValue])
                }
            }
            else {
                if (arr1SecondValue < arr2SecondValue) {
                    arr.push([arr1FirstValue, arr2SecondValue])
                } else {
                    arr.push([arr1FirstValue, arr1SecondValue])
                }
            }
        }
    })

Пробовал, но не вышло

[Василий Банников]

fillpower, Это код. А где алгоритм решения?

[fillpower]

Василий Банников, примерно вот так вышло)

[fillpower]

Василий Банников, я пытался...

[Василий Банников]

fillpower, а если блоксхемой? Или человеческим языком описать?

Answer 1

[Роман Якимчук]

const a = [[8, 12], [17, 22]];
const b = [[5, 11], [14, 18], [20, 23]];

const result = a.reduce((acc, rangeA) => {
  
  return b.reduce((list, rangeB) => {

    if (rangeA[0] >= rangeB[1] || rangeA[1] <= rangeB[0]) {
      return list;
    }

    const from = Math.max(rangeA[0], rangeB[0]);
    const to = Math.min(rangeA[1], rangeB[1]);

    return [...list, [from, to]];
  }, acc);

}, []);

Comments

[fillpower]

Спасибо большое! Очень элегантное решение.

[Роман Якимчук]

fillpower Обновите страницу, там сравнение немного не то было

[Сергей Соколов]

неэффективно: по второму целиком проходится снова и снова.
Не используется то свойство, что оба массива отсортированы.

[WbICHA]

return [...list, [from, to]];

Роман Якимчук, серьёзно? На каждой итерации пересоздавать массив?

[Роман Якимчук]

Сергей Соколов, Нигде не написано что они должны быть сортированы J

[Роман Якимчук]

WbICHA, Вы придираетесь, решение без оптимизации, можно и `concat`, и `push` сделать, но исходно вопрос лишь в логике.

[WbICHA]

Роман Якимчук, подобные мелкие оптимизации вообще-то делаются на автомате в процессе написания простейшего кода, так что нет, я не придираюсь.

[WbICHA]

Роман Якимчук, спасибо, хорошая статья, только её стоило прочитать и вам:

However, I should be aware of what are the constraints of the software I’m writing. If I knew the list would accommodate a few pairs of elements and never grow in size, and if the sequence is in the heart of a process that potentially can block the render thread for too long, I would put more thinking on it.

Отличное уточнение, которое как раз под ваш случай.

Answer 2

[WbICHA]

Альтернативный вариант:

const arr1 = [[8, 12], [17, 22]];
  const arr2 = [[5, 11], [14, 18], [20, 23]];
  
  const result = arr1.reduce((acc, range1) => {
    arr2.forEach((range2) => {
      const rangeLength1 = range2[1] - range1[0];
      const rangeLength2 = range1[1] - range2[0];
      
      if(rangeLength1 < rangeLength2) {
        if(rangeLength1 < 0) {
          return;
        }
        
        acc.push([range1[0], range2[1]]);
        return;
      }
      
      if(rangeLength2 < 0) {
        return;
      }
      
      acc.push([range2[0], range1[1]]);
    });
    
    return acc;
  }, []);