DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

1288. Remove Covered Intervals

Description

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.
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 0 <= li <= ri <= 105
  • All the given intervals are unique.

Solutions

Solution 1

Intuition

  1. ascending sort by the start of interval, if start are equal then descending sort by the end of interval;
  2. store the biggest end point, and update it
  3. if end point smaller than the biggest end point, this interval is covered.

Code

class Solution {
public:
    static bool compare(vector<int>& a, vector<int>& b) {
        return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    }
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        if (intervals.size() == 1) {
            return 1;
        }
        sort(intervals.begin(), intervals.end(), compare);
        int end = intervals[0][1];
        int count = intervals.size();
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][1] <= end) {
                count--;
            } else {
                end = intervals[i][1];
            }
        }
        return count;
    }
};
Enter fullscreen mode Exit fullscreen mode

Complexity

  • Time: O(nLogn)
  • Space: O(1)

Top comments (0)