[!info] related notes

合并区间

分析

应该直接按照数组第一位升序，然后遍历每个数组，看 第二个数组的 第一位 和 第一个数组的第二位比较大小

解法

function merge(intervals: number[][]): number[][] {
    let sorted = intervals.sort((a, b) => a[0] - b[0]);

    let ans = [];
    let left = 0,right = 0;
    for (let i = 0; i < intervals.length; i++) {
        left = intervals[i][0];
        right = intervals[i][1];
        while (i < intervals.length - 1 && right >= intervals[i+1][0] ) {
            right = Math.max(right, intervals[i+1][1]);
            i++;
        }
        ans.push([left,right]);

    }
    
    return ans;
};

ai 给出算法，更优雅

function merge(intervals: number[][]): number[][] {
    // 1. 按照左边界从小到大排序
    intervals.sort((a, b) => a[0] - b[0]);

    // 2. 初始化结果数组，先将第一个区间放入
    let ans: number[][] = [];
    ans.push(intervals[0]);

    // 3. 从第二个区间开始遍历
    for (let i = 1; i < intervals.length; i++) {
        let current = intervals[i];
        // 获取结果数组中最后一个区间（即当前正在试图合并的区间）
        let lastMerged = ans[ans.length - 1];

        // 4. 判断是否重叠
        // 如果当前遍历的区间左边界 <= 最后一个合并区间的右边界，说明有重叠
        if (current[0] <= lastMerged[1]) {
            // 合并区间：更新右边界为两者的最大值
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // 没有重叠，说明上一个区间已经合并完毕，当前区间是一个新的开始
            ans.push(current);
        }
    }

    return ans;
};