435. Non-overlapping Intervals

Leetcode link

题目简介

/**
 * @param {number[][]} intervals
 * @return {number}
 */

题目给我们一个二维数字数组 intervals，数组元素代表一段范围

题目要求我们删除部分元素使得数组元素的范围互相不重复

最后返回删除最少元素的方案的删除个数

解题思路

本题核心在于要如何快速判断是否有重复

我们可以对 intervals 的元素第二项升序排序

这样一来，我们只需要循环对比下一个元素的第一项是否比上一个元素的第二项小即可判断是否重复

如果有重复，我们就把需要删除的元素 +1；否则更新上一个元素第二项的记录

Javascript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function (intervals) {
    const len = intervals.length
    intervals.sort((a, b) => a[1] - b[1])
    let last = intervals[0][1]
    let res = 0

    for (let i = 1; i < len; i++) {
        if (intervals[i][0] < last) {
            res++
        } else {
            last = intervals[i][1]
        }
    }

    return res
};

复杂度分析

时间

O(nlogn)

空间

O(1)