1288 Remove Covered Intervals

Leetcode

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

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

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

---

先进行排序，左边界小的排前面。左边界相同的情况下，右边界大的排前面。依次遍历，定义变量 max 为当前最右边界，如果某个区间右边界小于 max ，则这个区间是要去掉的，因为已经按照左边界排序了。如果它没被去掉，说明它的右边界大于当前的，更新 max 。对去掉的进行计数。

public int removeCoveredIntervals(int[][] intervals) {
    Arrays.sort(intervals, (arr1, arr2)->{
        if(arr1[0]==arr2[0]){
            return arr2[1]-arr1[1];
        } else {
            return arr1[0]-arr2[0];
        }
    });
    int max=0;
    int count=0;
    for(int[] arr:intervals){
        if(arr[1]<=max) count++;
        else max=arr[1];
    }
    return intervals.length-count;
}