NC37 合并区间

https://www.nowcoder.com/practice/69f4e5b7ad284a478777cb2a17fb5e6a (opens new window)

描述

给出一组区间，请合并所有重叠的区间。 请保证合并后的区间按区间起点升序排列。

示例1：

输入：
[[10,30],[20,60],[80,100],[150,180]]

返回值：
[[10,60],[80,100],[150,180]]

示例2：

输入：
[[0,10],[10,20]]

返回值：
[[0,20]]

解答

/*
 * function Interval(a, b){
 *   this.start = a || 0;
 *   this.end = b || 0;
 * }
 */

/**
 * 
 * @param intervals Interval类一维数组 
 * @return Interval类一维数组
 */
function merge( intervals ) {
    if (intervals.length === 0) {
        return [];
    }

    const sortedIntervals = sort(intervals);

    const result = [sortedIntervals[0]];

    sortedIntervals.forEach((item) => {
        const curr = result[result.length - 1];

        // 有交集，更新 end
        if (item.start <= curr.end) {
            curr.end = Math.max(item.end, curr.end)
        } else {
            result.push(item);
        }
    });

    return result;
}

function sort(intervals) {
    return intervals.sort((item1, item2) => {
        return item1.start - item2.start;
    });
}

module.exports = {
    merge : merge
};