leetcode 435题

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
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

思路

按照区间的结尾进行排序，每次选择最早的，且和前一个区间不重叠的区间。选取末尾最早的，就可以给后面留出更大的控件，共后面的区间选择。这里的做法使用的就是贪心的思想

代码

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function eraseOverlapIntervals(intervals) {
    if (intervals.length === 0) {
        return 0;
    }

    intervals.sort((a, b) => a[1] - b[1]);

    let res = 1;
    let pre = 0;

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= intervals[pre][1]) {
            res++;
            pre = i;
        } else if (intervals[i][1] < intervals[pre][1]) {
            pre = i;
        }
    }

    return intervals.length - res;
}

复杂度分析:

时间复杂度: O(NlogN)
空间复杂度：O(1)

FEATURED TAGS

前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList 复盘 QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python SVG

leetcode 435 无重叠区间

思路

代码

CATALOG

FEATURED TAGS

FRIENDS