[LeetCode]My Calendar II

这道题和Calendar I的区别是，如果对于book的范围[s, e]中的某一点被三种覆盖了我们才返回false，否则就仍然可以book。我们首先仍然可以延续之前用map维护从小到大不相交的一组interval的方法，区别是这里我们维护的这组interval是已经被二重覆盖的interval，我们称其为list。那么具体的做法是：

1. 对于一个新的interval i，我们首先扫一遍之前所插入过的所有interval，算出i和之前所有插入过的interval的相交的部分的集合，称为overlaps
2. 我们可以明确的一点是，只有这些overlaps中的interval可能造成triple booking。不在overlaps中的部分都没有造成double booking，更不可能和list中的某些interval重叠造成triple booking。
3. 对于overlaps中的interval，我们check list中的intervals看是否会造成triple booking。因为只要和list中的某个interval重叠就会肯定造成triple booking。如果没有的话，我们更新list即可

list的话我们还是想Calendar I一样用BST来存，空间复杂度O(n)，每次book的话时间复杂度也是O(n)，代码如下：

	class MyCalendarTwo {
	public:
	MyCalendarTwo() {
	}
	bool book(int start, int end) {
	vector<pair<int, int>> ops;
	for(const auto& p : m_v)
	{
	if(overlap(start, end, p.first, p.second))
	{
	auto op = getOverlap(start, end, p.first, p.second);
	if(tripleBook(op))return false;
	else ops.push_back(op);
	}
	}
	m_v.emplace_back(start, end);
	for(const auto& op : ops)m_tree[op.first] = op.second;
	return true;
	}
	private:
	vector<pair<int, int>> m_v;
	map<int, int> m_tree;
	bool overlap(int s1, int e1, int s2, int e2)
	{
	return min(e1, e2) > max(s1, s2);
	}
	pair<int, int> getOverlap(int s1, int e1, int s2, int e2)
	{
	return make_pair(max(s1, s2), min(e1, e2));
	}
	bool tripleBook(const pair<int, int>& interval)
	{
	int start = interval.first, end = interval.second;
	auto iter = m_tree.lower_bound(end);
	if(iter == m_tree.begin())return false;
	--iter;
	if(iter->second <= start)return false;
	return true;
	}
	};
	/**
	* Your MyCalendarTwo object will be instantiated and called as such:
	* MyCalendarTwo obj = new MyCalendarTwo();
	* bool param_1 = obj.book(start,end);
	*/

view raw My Calendar II_2.cpp hosted with ❤ by GitHub

除此之外，我们用line sweep也是可以解决这个问题的。插入新的区间之后，我们从左到右扫一遍然后看某一点是否出现了triple booking即可。每次book的话时间复杂度也是O(n)，代码如下：

	class MyCalendarTwo {
	public:
	MyCalendarTwo() {
	}
	bool book(int start, int end) {
	if(m_tree[start] >= 2)return false;
	++m_tree[start];
	--m_tree[end];
	int layer = 0;
	for(auto& p : m_tree)
	{
	layer += p.second;
	if(layer > 2)
	{
	--m_tree[start];
	++m_tree[end];
	return false;
	}
	}
	return true;
	}
	private:
	map<int, int> m_tree;
	};
	/**
	* Your MyCalendarTwo object will be instantiated and called as such:
	* MyCalendarTwo obj = new MyCalendarTwo();
	* bool param_1 = obj.book(start,end);
	*/

view raw My Calendar II_1.cpp hosted with ❤ by GitHub