JavaScript合并区间的算法

Question

举个例子:

有如下三个区间:

[
    [1,100],
    [50,200],
    [300,400],
    ...  //可以更多
]

现在需要一个算法来合并区间, 合并之后是:

[
    [1,200],
    [300,400],
    ...
]

就是说重合的区间是需要合并的, 这样的算法该怎么写? 大神们给点思路吧

Answer 1

function merge(intervals) {
    intervals.sort(function(a, b) {
        if (a[0] !== b[0])
            return a[0] - b[0];
        return a[1] - b[1];
    });
    var len = intervals.length,
        ans = [],
        start, end;

    for (var i = 0; i < len; i++) {
        var s = intervals[i][0],
            e = intervals[i][1];
        if (start === undefined)
            start = s, end = e;
        else if (s <= end)
            end = Math.max(e, end);
        else {
            var part = [start, end];
            ans.push(part);
            start = s;
            end = e;
        }
    }

    if (start !== undefined) {
        var part = [start, end];
        ans.push(part);
    }

    return ans;
};

var arr = [
    [1, 100],
    [50, 200],
    [300, 400]
]
console.log(merge(arr))

Answer 2

1.类似于插入排序。
2.把[1,100]插入新数组
3.插入[50,200]是，判断50是否小于100且大于1.

- 如果是，更新[1,100]为[1,200]。
- 如果50大于100，则插入新数组[50,200]
- 如果50小于100且小于1，则判断上一个数组。找到50大于等于第一个数，小于等于第二个数的数组。
    - 如果属于这种情况，需要依次更新后面的数组。

Answer 3

1. 没有小数且数值较小的情况，最简单的办法就是打表。做一个，读入数据的时候直接把区间之间的坐标赋值为true，输出的时候再扫描一遍表里面的坐标就行了。

2. 不打表的话，双重循环就行了，比较任意两个线段，一旦交叉直接合并就行了。

Answer 4

比想象中烦一点, 因为是乱序的, 区间可能各种交叉

Answer 5

算法思路：

1. 对区间按头排序（升序）

2. 从第一区间起取当前拟合并区间为a，

3. 取下一区间为b（如果没有b了则输出a，退出）

4. 如果a的尾 > b 的头 ,则合并为 a，且跳到3，
   否则输出a，把b作为a，且跳到3

这个适用于很多个区间的合并。

Answer 6

var p=[
    [1,100],
    [80,99],
    [101,250],
    [300,400],
    [350,600],
    [600,800]
]
console.log(p)

var re = [];
var tmp = p[0]
re.push(tmp);
for(var i=1;i<p.length;i++){
  if(tmp[1]>=p[i][0] && tmp[1]<p[i][1]){
    tmp[1]=p[i][1]
  } else if(tmp[1]<p[i][0]){
    re.push(p[i])
    tmp = p[i]
  }
}
console.log(re)

Answer 7

var a = [[70,100],[50,200],[300,400]]

// 重排后数组
var trueArray = [a[0]]

var length = a.length

for(var i = 1; i < length; i++) {
    // 分块描述解题思路
    var temp = trueArray[trueArray.length -1]
    var tempData = []

    // 如果两个相邻模块是否有交集，没有那么就直下push数组
    if(temp[1] < a[i][0]) {
        trueArray.push(a[i])
        continue
    }

    // 对应两个相邻模块 0 位置谁小取谁，1位置谁大取谁。
    
    if (temp[0] > a[i][0]) {
        tempData[0] = a[i][0]
    } else {
        tempData[0] = temp[0]
    }

    if (temp[1] < a[i][1]) {
        tempData[1] = a[i][1]
    } else {
        tempData[1] = temp[1]
    }

    // 这里不能用temp赋值，因为和原trueArray不在同一内存地址了
    trueArray[trueArray.length -1] = tempData
}

// 数学题思路清晰问题就很明显了
console.log(trueArray)