LeetCode 435 无重叠区间

题目

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路

首先先对这些区间根据结尾进行排序，得到排序数组

然后进行遍历，来删除区间，判断逻辑就是下一个区间的头是否小于前一个区间的尾。如果小于则重叠那么删除，如果不小于则不重叠，则该区间变成”前一个区间”，继续与下一个区间进行对比

代码

/*
 * @lc app=leetcode.cn id=435 lang=javascript
 *
 * [435] 无重叠区间
 */

// @lc code=start
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    var result = 0;
    //先根据结尾排序
    intervals.sort(function (a, b) {
        return a[1] - b[1];
    });
    //遍历,并查看是否重叠,重叠则删,且前一项保持;不重叠则下一项变成前一项
    //判断标准:下一项的开头比前一项的结尾小则重叠
    var j=0;
    pre=intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0]<pre) {
            result++;
        }
        else{
            pre=intervals[i][1];
        }
        
    }
    return result;
};
// @lc code=end