Группируйте сегменты, которые не перекрываются, и сохраняйте порядок

Question

Я пытаюсь решить интересную задачу (я запрограммирую ее на JavaScript, но это не имеет особого значения):

Допустим, есть несколько видео в виде сегментов по несколько секунд на разных уровнях y . Если видео перекрываются во времени, то тот, который находится в верхнем слое, будет виден при воспроизведении всех из них одновременно.

Теперь у меня много этих слоев (это проблема). Я хочу чтобы объединить несколько слоев, когда это возможно, так что в конце у меня будет такое же количество видео, визуально отображаемых таким же образом, но меньше слоев.

Я покажу вам изображение, которое даст лучшее понимание

На этом изображении я взял пример из 11 видео на 11 начальных слоях.

Например, мы видим, что 2 и 1 могут быть поместите на один и тот же слой, поскольку они не перекрываются, и визуально видео будут отображаться одинаково, но, например, 1 и 9 не могут быть объединены рядом ни на 9-м слое, ни на 1-м слое, так как 7 перекрывают и теряют порядок отображения (z -index)

Если я хочу изобразить это в коде:

const orderedSegments = [
  [15, 18],     // 1
  [0.3, 9],     // 2
  [4, 13],      // 3
  [8, 14],      // 4
  [1, 3],       // 5
  [16, 19.5],   // 6
  [4.1, 17.5],  // 7
  [0, 2.9],     // 8
  [2.9, 11],    // 9
  [12.5, 19.4], // 10
  [11.3, 12]    // 11
]

А вот как может выглядеть один из возможных результатов, который будет иметь только 5 слоев, но с таким же отображением: * 1 021 *

 const expectedLayers = [
      [[0.3, 9], [15, 18]],                  // 2, 1
      [[1, 3], [4, 13]],                     // 5, 3
      [[8, 14], [16, 19.5]],                 // 4, 6
      [[0, 2.9], [4.1, 17.5]],               // 8, 7
      [[2.9, 11], [11.3, 12], [12.5, 19.4]]  // 9, 11, 10
 ]

Я подумал отсортировать сегменты по длительности начала, а затем создать 1 слой и попытаться вставить в него как можно больше, а когда больше невозможно создать новый слой ... но я Я не уверен, как правильно сохранить порядок.

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

Спасибо за идеи.

Answer 1

Я заметил, что вы называете свои сегменты orderedSegments, хотя на самом деле это не так. Итак, чтобы устранить путаницу, я решил переименовать их в unOrderedSegments, а затем создать отдельный массив orderedSegments, в котором есть лог c о том, какие сегменты должны быть первыми.

Затем я написал немного вспомогательная функция isOverlapping(a, b), которая смотрит на два сегмента и решает, пересекаются ли они / перекрывают друг друга или нет.

Затем я создал массив layers, который будет содержать каждый слой как отдельный элемент (массив сегментов) .

Лог c прост, как описано в псевдокоде:

loop through each `segment` in `orderedSegments`:
    loop through each `layer` in `layers`:
        check if the `segment` is overlaping any of the segments in the current `layer'
        if not then insert the `segment` to the current `layer`
        if yes, then check with the other layers
        if we reach the end of layers but could not insert it in any,
           then add the segment to its own new layer

const unOrderedSegments = [
  [15, 18], // 1
  [0.3, 9], // 2
  [4, 13], // 3
  [8, 14], // 4
  [1, 3], // 5
  [16, 19.5], // 6
  [4.1, 17.5], // 7
  [0, 2.9], // 8
  [2.9, 11], // 9
  [12.5, 19.4], // 10
  [11.3, 12], // 11
];

const orderedSegments = unOrderedSegments.sort((a, b) => a[0] - b[0]);

const isOverlapping = (a, b) => {
  const check1 = a[0] > b[0] && a[0] < b[1];
  const check2 = b[0] > a[0] && b[0] < a[1];

  return check1 || check2;
};

const layers = [];

for (let i = 0; i < orderedSegments.length; i++) {
  const currentSegment = orderedSegments[i];

  let inserted = false;

  for (let j = 0; j < layers.length; j++) {
    const currentLayer = layers[j];
    let canBeInserted = true;
    for (let k = 0; k < currentLayer.length; k++) {
      const segment = currentLayer[k];

      if (isOverlapping(segment, currentSegment)) {
        canBeInserted = false;
        break;
      }
    }
    if (canBeInserted) {
      currentLayer.push(currentSegment);
      inserted = true;
      break;
    }
  }
  if (!inserted) {
    layers.push([currentSegment]);
  }
}

// print each layer on a spearate line 
// ( convert array to string )
layers.forEach((layer) => {
  let layerString = "";
  layer.forEach((segment) => {
    layerString += `[${segment[0]}-${segment[1]}]`;
  });
  console.log(layerString);
});

Answer 2

const orderedSegments = [
  [15, 18],     // 1
  [0.3, 9],     // 2
  [4, 13],      // 3
  [8, 14],      // 4
  [1, 3],       // 5
  [16, 19.5],   // 6
  [4.1, 17.5],  // 7
  [0, 2.9],     // 8
  [2.9, 11],    // 9
  [12.5, 19.4], // 10
  [11.3, 12]    // 11
]

// sort array by starting time (orderedSegments[i][0])
orderedSegments.sort((a, b) => {
  if(a[0] < b[0]) return -1;
  if(a[0] > b[0]) return 1;
  return 0;
});

const newSegments = [];
while(orderedSegments.length > 0) {
  // get first element of array
  let element = orderedSegments[0];
  // all "used" items will be removed. used items are marked with -1
  if(element[0] == -1) {
    orderedSegments.shift();
    break;
  }
  // newElementGroup represents a new layer
  let newElementGroup = [];
  newElementGroup.push(element);
  for(let i = 0; i < orderedSegments.length; i++) {
    if(orderedSegments[i][0] > element[1]) {
      element = orderedSegments[i].slice();
      newElementGroup.push(element);
      // mark element as "used"
      orderedSegments[i][0] = -1;
    }
  }
  newSegments.push(newElementGroup);
  // remove first element after creating a new layer until orderedSegments is empty
  orderedSegments.shift();
}

newSegments.forEach(element => console.info(element))

думаю, это должно помочь