Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    ############
    
    class Solution {
        public int removeCoveredIntervals(int[][] intervals) {
            Arrays.sort(intervals, (a, b) -> a[0] - b[0] == 0 ? b[1] - a[1] : a[0] - b[0]);
            int[] pre = intervals[0];
            int cnt = 1;
            for (int i = 1; i < intervals.length; ++i) {
                if (pre[1] < intervals[i][1]) {
                    ++cnt;
                    pre = intervals[i];
                }
            }
            return cnt;
        }
    }
    
  • // 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;
        }
    };
    
  • class Solution:
        def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
            intervals.sort(key=lambda x: (x[0], -x[1]))
            cnt, pre = 1, intervals[0]
            for e in intervals[1:]:
                if pre[1] < e[1]:
                    cnt += 1
                    pre = e
            return cnt
    
    ############
    
    # 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
    
  • func removeCoveredIntervals(intervals [][]int) int {
    	sort.Slice(intervals, func(i, j int) bool {
    		if intervals[i][0] == intervals[j][0] {
    			return intervals[j][1] < intervals[i][1]
    		}
    		return intervals[i][0] < intervals[j][0]
    	})
    	cnt := 1
    	pre := intervals[0]
    	for i := 1; i < len(intervals); i++ {
    		if pre[1] < intervals[i][1] {
    			cnt++
    			pre = intervals[i]
    		}
    	}
    	return cnt
    }
    

All Problems

All Solutions