删除被覆盖区间

删除被覆盖区间

https://leetcode-cn.com/problems/remove-covered-intervals/

排序并观察

依照惯例，按区间起点升序对区间排序，如果起点相同则按终点降序排序。

排序后，香菱区间的相对关系只有 3 个可能：

  1. 找到了覆盖的区间
  2. 区间相交，可以视作合并为一个更大的区间
  3. 区间不相交
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
func removeCoveredIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] == intervals[j][0] {
            return intervals[i][1] > intervals[j][1]
        } else {
            return intervals[i][0] < intervals[j][0]
        }
    })

    left, right := intervals[0][0], intervals[0][1]
    count := 0

    for i := 1; i < len(intervals); i++ {
        // 找到覆盖区间
        if intervals[i][0] >= left && intervals[i][1] <= right {
            count++
        }

        // 区间相交
        if intervals[i][0] >= left && intervals[i][1] > right {
            right = intervals[i][1]
        }

        // 区间不相交，更新起点终点
        if intervals[i][0] > right {
            left = intervals[i][0]
            right = intervals[i][1]
        }
    }

    return len(intervals) - count
}