组段不重叠并保持良好顺序

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层但具有相同显示的可能结果之一： 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

我注意到你打电话给你的区段，而实际上，它们不是。因此，为了消除任何混淆，我决定将它们重命名为，然后创建一个单独的数组，该数组具有一些关于哪些段应该首先出现的逻辑。orderedSegmentsunOrderedSegmentsorderedSegments

然后，我编写了一个小的辅助函数，该函数查看两个段并决定它们是否相交/重叠。isOverlapping(a, b)

然后，我创建了一个数组，它将每个层作为单独的元素（段数组）保存。layers

逻辑很简单，如伪代码中所述：

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

我想这应该可以解决问题