Description
Implement a MyCalendarTwo
class to store your events. A new event can be added
if adding
the event will
not cause a triple booking.
Your
class will have one 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 triple booking happens when three events have
some non-empty intersection (ie., there
is some time that is common
to all
3 events.)
For each call
to the method MyCalendar.book,
return true if the event can be added
to the calendar successfully
without causing a
triple 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 1
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
Explanation:
The first two events can
be booked. The third event can
be double booked.
The fourth event (5, 15) can't
be booked, because it would result
in a triple booking.
The fifth event (5, 10) can
be booked,
as it does
not use time 10 which
is already double booked.
The sixth event (25, 55) can
be booked,
as the time
in [25, 40) will
be double booked with the third event;
the time [40, 50) will
be single booked,
and the time [50, 55) will
be double booked with the second event.
Note
1.The number
of calls
to MyCalendar.book per test
case will be at most
1000.
2.In calls
to MyCalendar.book(start,
end), start
and end are integers
in the
range [
0,
10^
9].
Solution 1(C++)
class MyCalendar {
vector<pair<int, int>> books;
public:
bool book(
int start,
int end) {
for (pair<
int,
int> p : books)
if (max(p.first, start) < min(end, p.second))
return false;
books.push_back({start, end});
return true;
}
};
class MyCalendarTwo {
vector<pair<int, int>> books;
public:
bool book(
int start,
int end) {
MyCalendar overlaps;
for (pair<
int,
int> p : books) {
if (max(p.first, start) < min(end, p.second)) {
pair<
int,
int> overlapped = getOverlap(p.first, p.second, start, end);
if (!overlaps.book(overlapped.first, overlapped.second))
return false;
}
}
books.push_back({ start, end });
return true;
}
pair<
int,
int> getOverlap(
int s0,
int e0,
int s1,
int e1) {
return { max(s0, s1), min(e0, e1)};
}
};
Solution 2(C++)
class MyCalendar {
vector<pair<int, int>> books;
public:
MyCalendar(){
}
bool book(
int start,
int end){
for(pair<
int,
int> p : books){
if(max(p.first, start) < min(p.second, end))
return false;
}
books.push_back({start, end});
return true;
}
};
class MyCalendarTwo {
vector<pair<int, int>> books;
public:
MyCalendarTwo() {
}
bool book(
int start,
int end) {
MyCalendar* mycalendar =
new MyCalendar();
for(pair<
int,
int> p : books){
if(max(p.first, start) < min(p.second, end)){
pair<
int,
int> overlap = GetOverLap(p.first, p.second, start, end);
if(!mycalendar->book(overlap.first, overlap.second))
return false;
}
}
books.push_back({start, end});
delete mycalendar;
return true;
}
pair<
int,
int> GetOverLap(
int s0,
int e0,
int s1,
int e1){
int start=max(s0, s1);
int end=min(e0, e1);
return {start, end};
}
};
算法分析
这道题，按照题目的意思来就可以，关键是，编程实现。同类型的题目可以参考：LeetCode-729. My Calendar I。
解法一与解法二本质上相同，只是有一些地方不太一样。注意MyCalendar类的实例化方法。
程序分析
这道题很锻炼编程能力啊，首先说一点C++的类的实例化方法。
C++类的实例化方法有两种，一种是直接通过类名直接定义对象，另一种是new一个指针指向该类。
从栈实例化：如果直接通过类名定义一个对象的话，对象使用其成员变量和函数时是通过点的形式。从栈实例化对象，使用完之后，不需要我们自己去理睬，系统自动会将其占用的内存释放掉。从堆实例化：如果是通过指针定义对象的话，则是通过->来访问其变量和函数。结束需要delete指针，释放内存。从堆实例化对象，使用完后，我们一定要将这块内存释放掉。
此外，查看两个区间：[s0，e0]与[s1，e1]是否有交集，可如下：
if(
max(s0, s1) <
min(e0, e1))
那么对应的，获得两个区间的交集区间也可以如下：
{
max(s0, s1),
min(e0, e1)}
