leetcode 1288. Remove Covered Intervals

快来打我* 2022-08-28 14:41 21阅读 0赞

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.  
Example 2:

Input: intervals = \[\[1,4\],\[2,3\]\]  
Output: 1

Constraints:

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

删除完全覆盖的区间。  
先按照区间的长度排序，因为如果出现重合，肯定是长区间的保留，短区间的删除。  
考虑到数组才度在1000以内，直接暴力， O ( n 2 ) O(n^2) O(n2)可以出结果。

class itv { 
    public:
    	int li, ri;
    	itv(int li, int ri){ 
    		this->li = li;
    		this->ri = ri;
    	}
    	bool operator<(const itv& rhs) { 
    		return (this->ri - this->li) < (rhs.ri - rhs.li);
    	}
    };
    class Solution { 
    public:
    	int removeCoveredIntervals(vector<vector<int>>& intervals) { 
    		vector<itv> itvs;
    		set<int> removed;
    		for (int i = 0; i < intervals.size(); i++)
    		{ 
    			itvs.push_back(itv(intervals[i][0], intervals[i][1]));
    		}
    		sort(itvs.begin(), itvs.end());
    		for (int i = itvs.size() - 1; i >= 0; i--)
    		{ 
    			if (removed.find(i) != removed.end())
    			{ 
    				continue;
    			}
    			for (int j = i - 1; j >= 0; j--)
    			{ 
    				if (itvs[i].li <= itvs[j].li && itvs[i].ri >= itvs[j].ri)
    				{ 
    					removed.insert(j);
    				}
    			}
    		}
    		return intervals.size() - removed.size();
    	}
    };

解法2： O ( n l o g n ) O(nlogn) O(nlogn)

先按照左侧进行排序。  
顺序遍历，然后右侧维护一个目前看到的最大的right。  
对于相同li，只维护最大的right。也就是说，相同的起点只保留最大的右侧。  
对于后面的元素来说，之前遍历的结果保证存在至少一个区间是可用覆盖住\[li, right\]的。

class Solution { 
    public:
    int removeCoveredIntervals(vector<vector<int>>& A) { 
            int res = 0, left = -1, right = -1;
            sort(A.begin(), A.end());
            for (auto& v: A) { 
                if (v[0] > left && v[1] > right) { 
                    left = v[0];
                    ++res;
                }
                right = max(right, v[1]);
            }
            return res;
        }
    };