[LeetCode]Set Intersection Size At Least Two

这道题我们可以观察出如下几点，对于两个区间i1和i2：

1. 如果区间i1包含区间i2，那么我们可以直接将remove i1而不需要考虑它，因为最终结果i2肯定至少也有两个元素被选，那么i1肯定也满足条件
2. 如果i1和i2没有交集，那么两个区间各自取两个数
3. 如果i1和i2正好头尾相交，比如i1 = [1,3], i2 = [3,6]，那么我们只需要在交点处取一个，之后在i1和i2中各取一个
4. 如果i2和i2相交并且相交的区间大于等于2，我们只需要在相交的部分取两个即可

对于情况1，我们只需要做一个preprocess，用stack来帮我们remove包含的情况。具体做法是，我们按照start排序interval，如果当前栈顶元素i1.end 大于等于当前元素i2.end，我们pop出i1即可。这样可以保证我们不会出现1中情况。那么现在的问题是，对于2、3、4的情况，我们应该如何在区间中取数呢？

经过preprocess之后，现在已经不存在1的情况，我们按照start排序，然后依次取出interval。如果我们发现需要在当前区间取数，那么我们取尽量靠右边的数，这样的话，对于下一个区间，其能够重复利用的可能性是最大的。也就说，假设已经在i1中取了数并且满足题目要求，对于i2来说：

• 如果是情况2，我们在i2的最右端取两个数
• 如果是情况2和3：
• 假设区间覆盖的部分没有包含i1取的数，同情况2
• 假设区间覆盖的部分包含i1取的数：
• 如果包含了1个，在i2最右端取一个
• 如果包含了2个，i2就不要取了

也就是说，我们每次要记录并更新上一次取的两个数的位置。假设有n个区间，算法时间复杂度O(n * log n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int intersectionSizeTwo(vector<vector<int>>& intervals) {
	auto comp = [](const vector<int>& lhs, const vector<int>& rhs){return lhs[0] == rhs[0]? lhs[1] > rhs[1]: lhs[0] < rhs[0];};
	sort(intervals.begin(), intervals.end(), comp);
	//using stack to remove overlaps
	stack<pair<int, int>> stack;
	for(auto& interval : intervals)
	{
	while(stack.size() && stack.top().second >= interval[1])
	stack.pop();
	stack.push(make_pair(interval[0], interval[1]));
	}
	int count = 0, lastPos[2] = { INT_MAX, INT_MAX };
	while(stack.size())
	{
	auto interval = stack.top();
	stack.pop();
	if(interval.second < lastPos[0])
	{
	count += 2;
	lastPos[0] = interval.first;
	lastPos[1] = interval.first + 1;
	}
	else if(interval.second < lastPos[1])
	{
	count += 1;
	lastPos[1] = lastPos[0];
	lastPos[0] = interval.first;
	}
	}
	return count;
	}
	};

view raw Set Intersection Size At Least Two.cpp hosted with ❤ by GitHub