Как объединить перекрывающиеся интервалы?

Question

[daima]

Есть массив интервалов, надо объединить перекрывающиеся, т.е:

[[0, 33],[66, 80]] => [[0, 33],[66, 80]]

[[0, 33],[66, 80],[0, 66],[33, 100]] => [[0,100]]

Накидал код:

const data = [
        [0, 33],
        [66, 80],
        [0, 66],
        [33, 100]
      ];

      createDataForSlider = data =>
        data.reduce((prevVal, time) => {
          let isPrevValUpdated = false;

          const timeStart = time[0];
          const timeEnd = time[1];

          /* eslint no-param-reassign: ["error", { "ignorePropertyModificationsFor": ["prevVal"] }] */
          if (prevVal.length) {
            for (let i = 0, ii = prevVal.length; i < ii; i += 1) {
              let prevValCurrent = prevVal[i];

              if (timeStart >= prevValCurrent[0] && timeEnd <= prevValCurrent[1]) {
                isPrevValUpdated = true;
                break;
              }
              if (
                !isPrevValUpdated &&
                timeStart >= prevValCurrent[0] &&
                timeStart <= prevValCurrent[1]
              ) {
                prevValCurrent[1] = timeEnd;
                isPrevValUpdated = true;
                break;
              }
              if (
                !isPrevValUpdated &&
                timeEnd >= prevValCurrent[0] &&
                timeEnd <= prevValCurrent[1]
              ) {
                prevValCurrent[0] = timeStart;
                isPrevValUpdated = true;
                break;
              }

              //console.log("prevVal-", prevVal);
            }
          }
          if (!isPrevValUpdated) {
            prevVal.push([timeStart, timeEnd]);
          }
          return prevVal;
        }, []);

      createDataForSlider(data);

На выходе имею [[0, 100], [66, 80]]. Это потому что сперва диапазон [[0, 33]], потом [[0, 33],[66, 80]], потом [[0, 66], [66, 80]], потом [[0, 100], [66, 80]] как бы проверять и остальные диапазоны без зацикливания.

Comments

[alex]

[[0, 66],[66, 80]] - считаются перекрывающимися?

Answer 1

[0xD34F]

Сортируем интервалы по возрастанию нижней границы. Перебираем интервалы и сохраняем текущий интервал в случае если ничего не сохранено (т.е., нулевой интервал сохраняется всегда) или если нижняя граница текущего интервала превышает верхнюю границу последнего сохранённого; в противном случае проверяем, что верхняя граница последнего сохранённого интервала ниже верхней границе текущего, если да - обновляем последний сохранённый - заменяем его верхнюю границу на верхнюю границу текущего.

function mergeIntervals(intervals) {
  intervals = intervals.map(n => [...n]);

  if (intervals.length < 2) {
    return intervals;
  }

  intervals.sort((a, b) => a[0] - b[0]);

  const stack = [];

  intervals.forEach(n => {
    const top = stack[stack.length - 1];

    if (!top || top[1] < n[0]) {
      stack.push(n);
    } else if (top[1] < n[1]) {
      top[1] = n[1];
    }
  });

  return stack;
}

Comments

[daima]

Ого, ты молодец!

intervals = intervals.map(n => [...n]); - не понимаю только это зачем

[0xD34F]

Это копирование переданного в функцию массива, чтобы не испортить оригинал - так как выполняется сортировка, удаление нулевого элемента, изменение верхних границ интервалов.

[daima]

0xD34F,

а почему не intervalsCope = ...intervals

[0xD34F]

Чё? Не понял вашего вопроса.

[daima]

0xD34F, ну, раз нам нужна копия массива почему бы вместо intervals = intervals.map(n => [...n]) не сделать intervalsCopy = ...intervals

Зы. на собеседованиях любят спрашивать про сложность алгоритма. Как ее определить и какая она для этого кода?

[0xD34F]

почему бы вместо intervals = intervals.map(n => [...n]) не сделать intervalsCopy = ...intervals

Во-первых - потому что это синтаксически некорректно, вы бы разобрались, как использовать spread. Во-вторых - элементы массива сами являются массивами, так что при таком подходе они останутся оригинальными.

сложность алгоритма. Как ее определить...

Предлагаю погуглить.

...и какая она для этого кода?

N * log N