合并 2 组区间，同时将每个区间从 set1 约束到 set2 的边界

Question

这是一张说明我的意思的图片：

基本上我想将 set1 合并到 set2 中，但是 set1 的每个间隔都不允许存在，除非它包含在 set2 的间隔范围内。

非常感谢任何建议！

PS：我的下一个任务是弄清楚如何合并 n 数量的 *set1*s（即可能相互重叠的绿色层）进入 set2 并应用相同的规则...但我会先从这个开始！

Answer 1

将 set2 中的所有间隔添加到结果中。
将 set1 中的所有间隔添加到结果中，如果它们不完全适合 set2 的间隔，则“剪切”或完全删除它们。
合并结果集中的所有重叠区间。

要有效地实施第二步，您可以按第一个坐标对 set2 中的间隔进行排序并使用二进制搜索。对于第 3 步 https://www.geeksforgeeks.org/merging-intervals/

Answer 2

这是 JavaScript 中用于此类合并的算法 -- 它应该很容易在其他编程语言中重现：

function merge(segments1, segments2) {
    const result = [];
    let i = -1, start1 = -Infinity, end1 = -Infinity, 
        j = -1, start2 = -Infinity; end2 = -Infinity;
    while (i < segments1.length || j < segments2.length) {
        if (end1 <= start2) { // get next from segments1
            i++;
            start1 = i < segments1.length ? segments1[i][0] : Infinity;
            end1 = i < segments1.length ? segments1[i][1] : Infinity;
        } else if (end2 <= start1) { // flush and get next from segments2
            if (start2 < end2) result.push([start2, end2]);
            j++;
            start2 = j < segments2.length ? segments2[j][0] : Infinity;
            end2 = j < segments2.length ? segments2[j][1] : Infinity;
        } else { // overlap
            if (start2 < start1) {
                result.push([start2, start1]);
                start2 = start1;
            }
            start1 = Math.min(end2, end1);
            result.push([start2, start1]);
            start2 = start1;
        }
    }
    return result;
}

// Sample input
const segments1 = [[6, 7], [8, 11], [12, 14], [15, 18], [19, 20], [22, 23], 
                   [25, 26], [27, 28], [30, 31], [33, 35]],
      segments2 = [[6, 10], [11, 14], [16, 17], [18, 21], [22, 24], [24, 26],
                   [27, 28], [29, 31], [33, 34], [35, 36]];
// Merge and output
const result = merge(segments1, segments2);
console.log(JSON.stringify(result));

要合并多组段，您只需像这样调用上面的函数：

merged = merge(green1, grey)
merged = merge(green2, merged)
merged = merge(green3, merged)
// ... etc

合并 2 组区间，同时将每个区间从 set1 约束到 set2 的边界

Merge 2 sets of intervals while constraining each interval from set1 to the bounds of set2

algorithm

intervals

overlap