Bruteforce or Line Sweep Algorithms to 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.

Constraints:
1 <= intervals.length <= 1000
0 <= intervals[i][0] < intervals[i][1] <= 10^5
intervals[i] != intervals[j] for all i != j

Hints:
How to check if an interval is covered by another?
Compare each interval to all others and check if it is covered by any interval.

Bruteforce Algorithm to Remove Covered Interval

Let’s use brute-force algorithm, which is the most intuitive solution. Brute force all possible pairs of intervals in O(N^2) time, then we use a vector to mark the validity of the intervals. A interval is set to be covered if its both ends are completely inside another one. Then, the result would be just to count the number of valid intervals in the boolean array – which we can use the std::accumulate if we want to avoid the for-loops (or while).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<bool> good(n, true);
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j < n; ++ j) {
                auto a = intervals[i];
                auto b = intervals[j];
                if (a[0] >= b[0] && a[1] <= b[1]) {
                    good[i] = false;
                } else if (b[0] >= a[0] && b[1] <= a[1]) {
                    good[j] = false;
                }
            }
        }
        return std::accumulate(begin(good), end(good), 0, [](int a, bool b) {
            return a + (b == true);
        });
    }
};

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<bool> good(n, true);
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j < n; ++ j) {
                auto a = intervals[i];
                auto b = intervals[j];
                if (a[0] >= b[0] && a[1] <= b[1]) {
                    good[i] = false;
                } else if (b[0] >= a[0] && b[1] <= a[1]) {
                    good[j] = false;
                }
            }
        }
        return std::accumulate(begin(good), end(good), 0, [](int a, bool b) {
            return a + (b == true);
        });
    }
};

The brute force‘s time complexity is O(N^2) and the space requirement is O(N). As the problem statement says, the input array of intervals contains at most 1000, O(N^2) would be too slow.

Line Sweep Algorithm to Remove Covered Interval

Let’s sort the intervals first by the lower point, which if it is equal, then we put the one first with a bigger upper point. For example, [1, 2], [1, 5] and [2, 3] are sorted.

Then, we check if the current interval’s upper-bound is larger than the previous endpoint – which we need to increment the answer as the current interval is not covered. Also, when need to update the previous interval upper-bound accordingly. For example, [2, 3] is covered as 3 is smaller than previous end which is 5.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(begin(intervals), end(intervals), [](auto &a, auto &b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });
        int count = 1;        
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++ i) {
            if (intervals[i][1] > end) {
                count ++;
                end = intervals[i][1];
            }
        }
        return count;
    }
};

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        sort(begin(intervals), end(intervals), [](auto &a, auto &b) {
            return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
        });
        int count = 1;        
        int end = intervals[0][1];
        for (int i = 1; i < intervals.size(); ++ i) {
            if (intervals[i][1] > end) {
                count ++;
                end = intervals[i][1];
            }
        }
        return count;
    }
};

The time complexity is O(N.LogN) as the sorting dominates. And the space requirement is O(1) constant – as we are assuming the sorting does not require additional space e.g. iterative Quick Sorting Algorithm.

–EOF (The Ultimate Computing & Technology Blog) —