JavaScript合并区间的算法

wolfx 2016年09月19日提问
0

举个例子:

有如下三个区间:

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

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

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

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

5个回答

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

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

- 如果是,更新[1,100]为[1,200]。
- 如果50大于100,则插入新数组[50,200]
- 如果50小于100且小于1,则判断上一个数组。找到50大于等于第一个数,小于等于第二个数的数组。
    - 如果属于这种情况,需要依次更新后面的数组。
0
  1. 没有小数且数值较小的情况,最简单的办法就是打表。做一个,读入数据的时候直接把区间之间的坐标赋值为true,输出的时候再扫描一遍表里面的坐标就行了。

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

0

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

0

算法思路:

  1. 对区间按头排序(升序)

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

  3. 取下一区间为b(如果没有b了则输出a,退出)

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

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

撰写答案