Bruteforce or Line Sweep Algorithms to Remove Covered Intervals

  • 时间:2020-09-13 14:33:25
  • 分类:网络文摘
  • 阅读:115 次

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) —

推荐阅读:
站长赚钱方法 联盟广告赚钱方法  “时刻”和“时间”有什么不同?  互质的两个数一定是质数吗?  两个质数的和为奇数,为什么必有一个为2?  第15届华杯赛决赛小学组试题解析三(A卷)  原来有多少人?  用两种思路解决一个问题  工具箱的表面积和体积如何计算?  乙将比丙领先多少米?  求两袋糖的重量之和 
评论列表
添加评论