扫描线

只检查终点和起点

1.Merge Intervals （ LeetCode 56 ）

时间88击败 内存99击败

var merge = function(intervals) {
    const result = []

    intervals.sort((a, b) => a[0] - b[0])
    intervals.forEach(item => {
        const len = result.length
        if(!len || result[len - 1][1] < item[0]) {
            result.push(item)
        } else {
            result[len - 1][1] = Math.max(result[len - 1][1], item[1])
        }
    })
    return result
};
// 每次都查找前一个区间与后一个区间是否有重叠

2.Insert Interval （ LeetCode 57 ）

var insert = function(intervals, newInterval) {
    const res = []
    let i = 0
    const len = intervals.length

    // 找出 每个框右侧 < new左侧，找出左侧不重叠
    while(i < len && intervals[i][1] < newInterval[0]) {
        res.push(intervals[i])
        i++
    }

    // 找出剩余 每个框左侧 <= new右侧，找出所有重叠，扩宽new左右边界
    while(i < len && intervals[i][0] <= newInterval[1]) {
        newInterval[0] = Math.min(intervals[i][0], newInterval[0])
        newInterval[1] = Math.max(intervals[i][1], newInterval[1])
        i++
    }
    res.push(newInterval)

    // 找出剩余 右侧不重叠
    while(i < len) {
        res.push(intervals[i])
        i++
    }

    return res
};

1272. Remove Interval
1273. Non-overlapping Intervals
1274. Remove Covered Intervals
1275. Data Stream as Disjoint Intervals
1276. Meeting Scheduler (返回最早的common slot，有长度限制）
1277. Interval List Intersections (返回所有的common slot, 无长度限制)
1278. Employee Free Time
1279. The Skyline Problem