[LeetCode]My Calendar I

假设当前插入的interval为[start, end)，那么我们要做的是查找之前插入的interval有没有overlap的部分。做法很多，可以维护一个按照start从小到大sorted的list，list当中每个interval都不相交。每次插入interval i1的时候二分法查找小于end的最大start值对应的interval i2，看i2是否和i1相交即可。维护sorted的list的代价太大，我们每一次插入都需要保证list仍然是sorted的，那么我们可以改用BST来存，key为start，value为end即可，思路是一样的。时间复杂度O(log n)，n为intervals的总数。代码如下：

	class MyCalendar {
	public:
	MyCalendar() {
	}
	bool book(int start, int end) {
	if(m_tree.empty()){ m_tree[start] = end; return true; }
	auto iter = m_tree.lower_bound(end);
	if(iter == m_tree.begin()){ m_tree[start] = end; return true; }
	--iter;
	if(iter->second <= start)
	{
	m_tree[start] = end;
	return true;
	}
	else return false;
	}
	private:
	map<int, int> m_tree;
	};
	/**
	* Your MyCalendar object will be instantiated and called as such:
	* MyCalendar obj = new MyCalendar();
	* bool param_1 = obj.book(start,end);
	*/

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