Formatted question description: https://leetcode.ca/all/1288.html

1288. Remove Covered Intervals (Medium)

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.

Related Topics:
Greedy, Sort, Line Sweep

Solution 1.

// OJ: https://leetcode.com/problems/remove-covered-intervals/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
        int ans = A.size(), e = INT_MIN;
        for (auto &r : A) {
            if (r[1] <= e) --ans;
            else e = r[1];
        }
        return ans;
    }
};

Java

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] array1, int[] array2) {
                if (array1[0] != array2[0])
                    return array1[0] - array2[0];
                else
                    return array1[1] - array2[1];
            }
        });
        int length = intervals.length;
        boolean[] remove = new boolean[length];
        for (int i = 0; i < length; i++) {
            int[] interval1 = intervals[i];
            for (int j = i + 1; j < length; j++) {
                int[] interval2 = intervals[j];
                if (interval2[1] <= interval1[1])
                    remove[j] = true;
                if (interval2[0] > interval1[1])
                    break;
            }
        }
        int removeCount = 0;
        for (int i = 0; i < length; i++) {
            if (remove[i])
                removeCount++;
        }
        return length - removeCount;
    }
}

// OJ: https://leetcode.com/problems/remove-covered-intervals/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& A) {
        sort(begin(A), end(A), [](auto &a, auto &b) { return a[0] != b[0] ? a[0] < b[0] : a[1] > b[1]; });
        int ans = A.size(), e = INT_MIN;
        for (auto &r : A) {
            if (r[1] <= e) --ans;
            else e = r[1];
        }
        return ans;
    }
};

# 1288. Remove Covered Intervals
# https://leetcode.com/problems/remove-covered-intervals/

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        
        n = len(intervals)
        res = 0
        
        for i in range(n):
            a,b = intervals[i]
            check = True
            for j in range(n):
                if i != j:
                    c,d = intervals[j]
                    
                    if c <= a and b <= d: 
                        check = False
                        break
            
            if check: res += 1
        
        return res

    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        res = right = 0
        
        intervals.sort(key = lambda x:(x[0],-x[1]))
        
        for start,end in intervals:
            res += end > right
            right = max(right, end)
        
        return res

1288 - Remove Covered Intervals

1288. Remove Covered Intervals (Medium)

Solution 1.

All Problems

All Solutions