LeetCode 435. 无重叠区间(贪心算法,动态规划)

简介: LeetCode 435. 无重叠区间(贪心算法,动态规划)

435. 无重叠区间


贪心解法

思路

首先将区间按右端点大小升序排序。那么第一个的右边界最小,给到下一个区间留的空间就更大。


局部最优:优先选择右边界小的区间,所以从左向右遍历,留给下一个区间的空间大,从而避免交叉


全局最优:选取最多的非交叉区间


特殊情况:首区间是 [2,3],[1,3] 排序后应该剔除哪个?对于这题来说其实都是一样的,可以任意选择,因为无论选择哪一个对于下一个区间的影响都是一样的,下一个区间只考虑其左端点是否小于首区间右端点,不在意首区间左端点的位置。


代码实现

class Solution
{
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), cmp);
        int pre = intervals[0][1], removed = 0;
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[i][0] < pre)
            {
                removed++;
            }
            else
            {
                pre = intervals[i][1];
            }
        }
        return removed;
    }
};


复杂度分析

时间复杂度:O(nlogn),其中n是区间的数量。我们需要O(nlogn)的时间对所有的区间按照右端点进行升序排序,并且需要O(n)的时间进行遍历。由于前者在渐进意义下大于后者,因此总时间复杂度为O(nlogn)。


空间复杂度:O(logn),即为排序需要使用的栈空间。


动态规划

思路

先将n个区间按右端点排序,然后使用动态规划方法求出区间最大值。令 fi 表示 以区间i为最后一个区间(包含i),可以选出的区间数量最大值


状态转移方程:

image.png

代码实现

class Solution
{
public:
    static bool cmp(vector<int> &a, vector<int> &b)
    {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), cmp);
        int n = intervals.size();
        vector f(n, 1);
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (intervals[j][1] <= intervals[i][0])
                {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
        }
        return n - *max_element(f.begin(), f.end());
    }
};


复杂度分析

时间复杂度:O ( n 2 )

空间复杂度:O ( n ) 即为存储所有状态 f i 需要的空间。

目录
相关文章
|
20天前
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
40 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
26天前
|
算法
LeetCode第57题插入区间
LeetCode第57题"插入区间"的解题方法,利用原区间集有序的特性,通过三步插入操作,有效实现了新区间的插入和重叠区间的合并。
LeetCode第57题插入区间
|
27天前
|
机器学习/深度学习 算法 Java
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
这篇文章介绍了基于贪婪技术思想的Prim算法和Dijkstra算法,包括它们的伪代码描述、Java源代码实现、时间效率分析,并展示了算法的测试用例结果,使读者对贪婪技术及其应用有了更深入的理解。
算法设计(动态规划应用实验报告)实现基于贪婪技术思想的Prim算法、Dijkstra算法
|
27天前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
|
1月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
34 6
|
1月前
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
39 2
|
1月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
35 1
|
1月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
32 1
|
1月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
55 0
|
1月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
29 0
下一篇
DDNS