Leetcode 1288 Remove Covered Intervals

    科技2022-07-17  153

    Leetcode 1288 Remove Covered Intervals

    题目思路

    题目

    Given a list of intervals, remove all intervals that are covered by another interval in the list.

    Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

    After doing so, return the number of remaining intervals.

    Example 1: Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

    Example 2: Input: intervals = [[1,4],[2,3]] Output: 1

    Example 3: Input: intervals = [[0,10],[5,12]] Output: 2

    Example 4: Input: intervals = [[3,10],[4,10],[5,11]] Output: 2

    Example 5: Input: intervals = [[1,2],[1,4],[3,4]] Output: 1

    Constraints:

    1 <= intervals.length <= 1000 intervals[i].length == 2 0 <= intervals[i][0] < intervals[i][1] <= 10^5 All the intervals are unique.

    思路

    法一

    考虑一种排序的方式,先按interval[0]从小到大排序,再按interval[1]从大到小排序,这样的话可以保证如果有包含关系的两个区间,被包含的一定在包含它的区间的后面出现(因为包含关系的两个区间A包含B,等价于A[0] < B[0], A[1] >= B[1] 或 A[0] = B[0], A[1] >= B[1], 前者因为A[0] < B[0]满足A排序在B前,后者因为A[1] >= B[1]满足A排序在B前)。 所以最后只要遍历,不断记录interval[1]的最大值,当当前interval[1]比最大值小时即为包含(因为该区间的左侧于之前的所有区间都满足包含条件,所以只要任一区间的右侧满足包含条件即为包含),计数扣1。

    class Solution { public int removeCoveredIntervals(int[][] intervals) { if (intervals == null || intervals.length == 0) return 0; int res = intervals.length; Arrays.sort(intervals, (o1, o2) -> { if (o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]); return Integer.compare(o1[0], o2[0]); }); int right = -1; for (int[] interval : intervals) { if (interval[1] <= right) res--; right = Math.max(right, interval[1]); } return res; } }

    法二 参考Leetcode Sample代码,直接两层loop搜索intervals[i]是否包含intervals[j]或intervals[j]是否包含intervals[i]。

    class Solution { public int removeCoveredIntervals(int[][] intervals) { int len = intervals.length; for (int i = 0; i < intervals.length - 1; i++) { if (intervals[i] == null) continue; int a = intervals[i][0], b = intervals[i][1]; for (int j = i + 1; j < intervals.length; j++) { if (intervals[j] == null) continue; int c = intervals[j][0], d = intervals[j][1]; if (c <= a && b <= d) { len--; break; } else if (c >= a && b >= d) { intervals[j] = null; len--; } } } return len; } }
    Processed: 0.009, SQL: 8