ChunNote
0%

leetCode-435:Non-overlapping Intervals

发表于 分类于

问题描述

给定一个表示区间集合的二维数组，要求移除某些区间，使各个区间之间没有重叠，将最小的移除区间数返回。题目链接：**点我**

样例输入输出

输入：[[1,2],[2,3],[3,4],[1,3]]

输出：1

解释：移除区间 [1, 3]，剩下的区间 [1, 2], [2, 3], [3, 4] 不会重叠

输入：[[1,2],[2,3],[3,4]]

输出：0

问题解法

先将区间进行排序，然后依次遍历，判断当前区间是否要移除，判断的条件为：

  • 如果当前区间与上一个保留的区间重叠，则判断当前区间是否包含在上个保留区间中，如果被包含，则移除上个保留区间，通过将当前区间设置为上个保留区间
  • 如果当前区间没有与上个保留区间重叠，则更新当前区间为上个保留区间

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
    public int eraseOverlapIntervals(int[][] intervals)
    {
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] < b[0])
            {
                return -1;
            }

            if (a[0] > b[0])
            {
                return 1;
            }

            return a[1] - b[1];
        });

        int lastIndex = 0;
        int count = 0;
        for (int i = 1; i < intervals.length; i++)
        {
            if (intervals[i][0] >= intervals[lastIndex][0] && intervals[i][0] < intervals[lastIndex][1])
            {
                // 考虑：[[1, 5], [2, 3], [3, 4], [4, 5]] 的情况
                if (intervals[i][1] <= intervals[lastIndex][1])
                {
                    lastIndex = i;
                }
                count++;
            }
            else
            {
                lastIndex = i;
            }
        }

        return count;
    }
}