我的日程表 I（729. My Calendar I）

1 描述

Description

• Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.
• Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.
• A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)
• For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.
• Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example
MyCalendar();

• MyCalendar.book(10, 20); // returns true
• MyCalendar.book(15, 25); // returns false
• MyCalendar.book(20, 30); // returns true

Explanation:

• The first event can be booked. The second can’t because time 15 is already booked by another event.
• The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note

• The number of calls to MyCalendar.book per test case will be at most 1000.
• In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

2 代码

#include <iostream>
#include <map>
using namespace std;

class MyCalendar {
public:
	map<int, int> books;
	MyCalendar() {}
	
	bool book(int start, int end) {
		bool res = false;
		auto itS = books.end();
		auto itE = books.end();

		auto temp = books.begin();
		while (temp != books.end())
		{
			if (start < temp->second)
			{
				itS = temp;
				break;
			}
			temp++;
		}

		temp = books.end();
		while (temp != itS)
		{
			--temp;
			if (end > temp->first)
			{
				itE = temp;
				break;
			}
		}
		if (itE == books.end())
		{
			res = true;
			books.insert(make_pair(start, end));
		}
		return res;
	}
};

int main()
{
	MyCalendar* obj = new MyCalendar();
	bool res = obj->book(10, 20);
	cout << res << endl;
	res = obj->book(15, 25);
	cout << res << endl;
	res = obj->book(20, 30);
	cout << res << endl;
	res = obj->book(25, 35);
	cout << res << endl;

	system("pause");
    return 0;
}

3 解释

主要思路，找出所有与 “新计划” 相冲突的 “旧计划”

• “旧计划” 个数为 0，则证明不冲突；
• “旧计划” 个数大于 0，则证明冲突；