题解 | #合并区间#

如何使用双指针合并区间？

• 如果两个相邻的区间需要合并，那么此时前一个区间的末尾要大于后一个区间的开头，因此我们可以用一个指针用于遍历区间数组，还有一个指针指向原区间数组中的当前区间的开头，将当前区间的开头和合并区间数组的最后一个区间的末尾比较，来判断当前区间是否需要合并。
• 为了能方便判断相邻区间是否需要合并，需要先对区间数组按每个区间的第一个元素来进行排序。

如何使用贪心思想合并区间？

• 贪心思想属于动态规划思想中的一种，其基本原理是找出整体当中给的每个局部子结构的最优解，并且最终将所有的这些局部最优解结合起来形成整体上的一个最优解。
• 最小子问题为两个相邻区间是否能合并，则我们每次判断合并区间数组的最后一个区间是否需要和原区间数组的当前区间合并，如果需要合并则更改合并区间数组最后一个区间的最后一个元素，如果不需要合并则将原区间数组的当前区间添加到合并区间数组的末尾。

参考

https://blog.nowcoder.net/n/e6177985fbe94fc1ab58e42c38564273?f=comment

https://blog.nowcoder.net/n/15540cfa99a1448887609dd237a18c6a?f=comment

class Interval {
    start: number
    end: number
    constructor(start: number, end: number) {
        this.start = start 
        this.end = end 
    }
}



/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param intervals Interval类一维数组 
 * @return Interval类一维数组
 */
export function merge(intervals: Interval[]): Interval[] {
    // write code here
    const ret: Array<Interval> = [];
    
    if (intervals.length <= 1) {
        return intervals;
    }

    // 原数组各个区间之间可能没有排序，需要先排序，由于题目要求最后合并的区间按起点升序排列，因此可以按各个区间的起点排列区间
    intervals.sort((a: Interval, b: Interval): number => {
        return a.start - b.start;
    })
    ret.push(intervals[0]);  // 第一个区间加入结果中，用于后面的合并

    for (let i = 1; i < intervals.length; ++i) {
        if (intervals[i].start <= ret[ret.length-1].end) {
            ret[ret.length-1].end = Math.max(intervals[i].end, ret[ret.length-1].end);
        }
        else {
            ret.push(intervals[i]);
        }
    }

    return ret;
}