leetcode452,435
假设有intervals[][]这么一个二维数组,我们要找到其中的重叠区间个数:
解题思路:分两种情况讨论即可:
首先我们需要对区间进行一个排序,为了尽量让相邻的区间重叠,以便后续操作
1.如果当前区间的左边界和上个区间的右边界不重合,那么这两个区间肯定是不重合的
2.如果当前区间的左边界和上个区间的右边界重合,那么最好的情况下,只有这两个区间是重合的
如果只是简单的判断有多少个重叠区间:我们只需本区间和前一个区间比对即可
如果是求删除最小区间保证无重叠区间:如何判断第三个,乃至更多的区间与他们重合呢?这里我们就需要修改区间的边界值,已知两个区间重合之后,我们让当前区间的右边界取当前区间与前一个区间右边界的最小值。然后再回到上述循环中,最终我们就可以求出重叠区间。如下图
标签:边界,重合,当前,区间,贪心,重叠 From: https://www.cnblogs.com/kun1790051360/p/18182830