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

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`:&nbsp; &nbsp; loop through each `layer` in `layers`:&nbsp; &nbsp; &nbsp; &nbsp; check if the `segment` is overlaping any of the segments in the current `layer'&nbsp; &nbsp; &nbsp; &nbsp; if not then insert the `segment` to the current `layer`&nbsp; &nbsp; &nbsp; &nbsp; if yes, then check with the other layers&nbsp; &nbsp; &nbsp; &nbsp; if we reach the end of layers but could not insert it in any,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;then add the segment to its own new layerconst unOrderedSegments = [&nbsp; [15, 18], // 1&nbsp; [0.3, 9], // 2&nbsp; [4, 13], // 3&nbsp; [8, 14], // 4&nbsp; [1, 3], // 5&nbsp; [16, 19.5], // 6&nbsp; [4.1, 17.5], // 7&nbsp; [0, 2.9], // 8&nbsp; [2.9, 11], // 9&nbsp; [12.5, 19.4], // 10&nbsp; [11.3, 12], // 11];const orderedSegments = unOrderedSegments.sort((a, b) => a[0] - b[0]);const isOverlapping = (a, b) => {&nbsp; const check1 = a[0] > b[0] && a[0] < b[1];&nbsp; const check2 = b[0] > a[0] && b[0] < a[1];&nbsp; return check1 || check2;};const layers = [];for (let i = 0; i < orderedSegments.length; i++) {&nbsp; const currentSegment = orderedSegments[i];&nbsp; let inserted = false;&nbsp; for (let j = 0; j < layers.length; j++) {&nbsp; &nbsp; const currentLayer = layers[j];&nbsp; &nbsp; let canBeInserted = true;&nbsp; &nbsp; for (let k = 0; k < currentLayer.length; k++) {&nbsp; &nbsp; &nbsp; const segment = currentLayer[k];&nbsp; &nbsp; &nbsp; if (isOverlapping(segment, currentSegment)) {&nbsp; &nbsp; &nbsp; &nbsp; canBeInserted = false;&nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; if (canBeInserted) {&nbsp; &nbsp; &nbsp; currentLayer.push(currentSegment);&nbsp; &nbsp; &nbsp; inserted = true;&nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; }&nbsp; }&nbsp; if (!inserted) {&nbsp; &nbsp; layers.push([currentSegment]);&nbsp; }}// print each layer on a spearate line&nbsp;// ( convert array to string )layers.forEach((layer) => {&nbsp; let layerString = "";&nbsp; layer.forEach((segment) => {&nbsp; &nbsp; layerString += `[${segment[0]}-${segment[1]}]`;&nbsp; });&nbsp; console.log(layerString);});

Answer 2

const orderedSegments = [&nbsp; [15, 18],&nbsp; &nbsp; &nbsp;// 1&nbsp; [0.3, 9],&nbsp; &nbsp; &nbsp;// 2&nbsp; [4, 13],&nbsp; &nbsp; &nbsp; // 3&nbsp; [8, 14],&nbsp; &nbsp; &nbsp; // 4&nbsp; [1, 3],&nbsp; &nbsp; &nbsp; &nbsp;// 5&nbsp; [16, 19.5],&nbsp; &nbsp;// 6&nbsp; [4.1, 17.5],&nbsp; // 7&nbsp; [0, 2.9],&nbsp; &nbsp; &nbsp;// 8&nbsp; [2.9, 11],&nbsp; &nbsp; // 9&nbsp; [12.5, 19.4], // 10&nbsp; [11.3, 12]&nbsp; &nbsp; // 11]// sort array by starting time (orderedSegments[i][0])orderedSegments.sort((a, b) => {&nbsp; if(a[0] < b[0]) return -1;&nbsp; if(a[0] > b[0]) return 1;&nbsp; return 0;});const newSegments = [];while(orderedSegments.length > 0) {&nbsp; // get first element of array&nbsp; let element = orderedSegments[0];&nbsp; // all "used" items will be removed. used items are marked with -1&nbsp; if(element[0] == -1) {&nbsp; &nbsp; orderedSegments.shift();&nbsp; &nbsp; break;&nbsp; }&nbsp; // newElementGroup represents a new layer&nbsp; let newElementGroup = [];&nbsp; newElementGroup.push(element);&nbsp; for(let i = 0; i < orderedSegments.length; i++) {&nbsp; &nbsp; if(orderedSegments[i][0] > element[1]) {&nbsp; &nbsp; &nbsp; element = orderedSegments[i].slice();&nbsp; &nbsp; &nbsp; newElementGroup.push(element);&nbsp; &nbsp; &nbsp; // mark element as "used"&nbsp; &nbsp; &nbsp; orderedSegments[i][0] = -1;&nbsp; &nbsp; }&nbsp; }&nbsp; newSegments.push(newElementGroup);&nbsp; // remove first element after creating a new layer until orderedSegments is empty&nbsp; orderedSegments.shift();}newSegments.forEach(element => console.info(element))我想这应该可以解决问题