[LeetCode]My Calendar III

这道题更general了，每次插入一个区间，我们要返回当前被覆盖最多的层数。首先延续My Calendar II中line sweep的方法仍然是可以做的。空间复杂度O(n)，book的时间复杂度也是O(n)。代码如下：

	class MyCalendarThree {
	public:
	MyCalendarThree() {
	}
	int book(int start, int end) {
	m_calendar[start] += 1;
	m_calendar[end] -= 1;
	return getCount();
	}
	private:
	map<int, int> m_calendar;
	int getCount()
	{
	int curr = 0, res = 0;
	for (const auto& p : m_calendar)
	{
	curr += p.second;
	res = curr > res ? curr : res;
	}
	return res;
	}
	};
	/**
	* Your MyCalendarThree object will be instantiated and called as such:
	* MyCalendarThree obj = new MyCalendarThree();
	* int param_1 = obj.book(start,end);
	*/

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

此外，这也是一道很明显的range query的题目，我们可以用segment tree来解决。具体来说，叶节点存的是当前index对应被覆盖了多少次，非叶节点存的就是这个区间对应的最多的被覆盖的次数。每次插入[s , e]的话就相当于对[s , e]进行range update，区间里的每一个元素加1。区间更新我们用lazy propagation，具体参考上面给出的链接。查询的话直接查根节点储存的信息即可。时间复杂度O(log n)，空间复杂度O(n)，代码如下：

	class Node
	{
	public:
	int start, end, lazy;
	int cnt;//max K in [start, end]
	Node* left, *right;
	Node(int s, int e)
	{
	start = s;
	end = e;
	cnt = 0;
	lazy = 0;
	left = nullptr;
	right = nullptr;
	}
	Node* getLeft()
	{
	int mid = start + (end - start) / 2;
	if (!left)left = new Node(start, mid);
	return left;
	}
	Node* getRight()
	{
	int mid = start + (end - start) / 2;
	if (!right)right = new Node(mid + 1, end);
	return right;
	}
	void insert(int s, int e)
	{
	if (lazy)propagate();
	if (s > end || e < start)return;
	else if (start >= s && end <= e)
	{
	++cnt;
	if (start != end)
	{
	++getLeft()->lazy;
	++getRight()->lazy;
	}
	}
	else
	{
	getLeft()->insert(s, e);
	getRight()->insert(s, e);
	cnt = max(getLeft()->cnt, getRight()->cnt);
	}
	}
	void clear()
	{
	if (left)left->clear();
	if (right)right->clear();
	delete this;
	}
	private:
	void propagate()
	{
	if (start != end)
	{
	getLeft()->lazy += lazy;
	getRight()->lazy += lazy;
	}
	cnt += lazy;
	lazy = 0;
	}
	};
	class MyCalendarThree {
	public:
	MyCalendarThree() {
	root = new Node(0, 1000000000);
	}
	~MyCalendarThree()
	{
	root->clear();
	}
	int book(int start, int end) {
	root->insert(start, end - 1);
	return root->cnt;
	}
	private:
	Node* root;
	};

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