Bruteforce or Line Sweep Algorithms to Remove Covered Intervals

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

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

推荐阅读:
seo-网站权重怎么提高?  万词霸屏与SEO优化合二为一才能给企业带来真实效益  熟知百度蜘蛛原理,按照优化规则才能做好seo优化  SEO关键词排名优化原理是什么?  织梦程序如何调用自定义字段?  旅途遇见美  不再遗失的美好  美丽的三亚作文600字  最后的六一作文650字  疲惫并快乐着 
评论列表
添加评论