题解 | #合并区间#

先排序(这里的复杂度取决于 sort 函数，约为: O(nlogn) )，再从第一个元素开始遍历合并(时间复杂度为 O(n)) , 空间复杂度为 O(Val)

1. 若 next 的区间被 pre 所包含，则 pre 直接与下一个元素进行合并
2. 若 pre 的区间大值比 next 的区间小值还要小，则把 pre 赋值为 next
3. 若 pre 的区间大值在 next 的区间小值与大值之间，则修改 pre 的大值为 next 的区间大值

/*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
    let len = intervals.length;
    if(len <= 1){
        return intervals;
    }

    intervals = intervals.sort((a, b)=>{
        return a.start - b.start;
    });

    let result = [], pre:any = intervals[0], next;
    for(let i = 1; i < len; i++){
        next = intervals[i];
        if(pre.end >= next.start){
            if(pre.end < next.end){
                pre.end = next.end;
            }
        }else{
            result.push(pre);
            pre = next;
        }
    }
    result.push(pre);
    return result;
}