435.无重叠区间

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    // 贪心算法
    // 移除区间数量最少=留下的不重叠区间最多=预订会议问题

    // 先按右端点排序
    // 为什么是右端点不是左端点？如果按照左端点排序，我们能找到最先开始的会议，但最先开始的会议不一定最先结束。
    // 举个左端点排序的例子[[1,100],[2,10],[11,20],[21,30]]
    // 如果以[1,100]为首个区间，最大不重叠区间数量为1；但是以[2,10]为首个区间，最大不重叠区间数量为3
    intervals.sort((a, b) => a[1] - b[1])

    let n = intervals.length
    let right = intervals[0][1] // 安排第一个会议
    let count = 1 // 会议数量
    for (let i = 1; i < n; i++) {
        // 如果下一个会议的开始时间比上一个要晚，则可以安排。即左端点大于等于上一个右端点
        if (intervals[i][0] >= right) {
            count++ // 会议数量+1
            right = intervals[i][1] // 更新会议结束时间
        }
    }
    // 剩下的就是要移除的数量
    return n - count
};

// console.log(eraseOverlapIntervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
// console.log(eraseOverlapIntervals([[1,2],[1,2],[1,2]]))
console.log(eraseOverlapIntervals([[1, 100], [11, 22], [1, 11], [2, 12]]))