729 My Calendar I 我的日程安排表 I
Description:
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.
A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).
The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendar class:
MyCalendar() Initializes the calendar object.
boolean book(int start, int end) Returns 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.
Example:
Example 1:
Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]
Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
Constraints:
0 <= start < end <= 10^9
At most 1000 calls will be made to book.
題目描述:
實(shí)現(xiàn)一個(gè) MyCalendar 類來存放你的日程安排。如果要添加的時(shí)間內(nèi)沒有其他安排，則可以存儲(chǔ)這個(gè)新的日程安排腻菇。
MyCalendar 有一個(gè) book(int start, int end)方法状勤。它意味著在 start 到 end 時(shí)間內(nèi)增加一個(gè)日程安排三圆，注意爬立，這里的時(shí)間是半開區(qū)間，即 [start, end), 實(shí)數(shù) x 的范圍為司顿， start <= x < end伴找。
當(dāng)兩個(gè)日程安排有一些時(shí)間上的交叉時(shí)（例如兩個(gè)日程安排都在同一時(shí)間內(nèi)）盈蛮，就會(huì)產(chǎn)生重復(fù)預(yù)訂。
每次調(diào)用 MyCalendar.book方法時(shí)技矮，如果可以將日程安排成功添加到日歷中而不會(huì)導(dǎo)致重復(fù)預(yù)訂抖誉，返回 true殊轴。否則，返回 false 并且不要將該日程安排添加到日歷中寸五。
請(qǐng)按照以下步驟調(diào)用 MyCalendar 類: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)
示例 :
示例 1:
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
解釋:
第一個(gè)日程安排可以添加到日歷中. 第二個(gè)日程安排不能添加到日歷中，因?yàn)闀r(shí)間 15 已經(jīng)被第一個(gè)日程安排預(yù)定了耿币。
第三個(gè)日程安排可以添加到日歷中梳杏，因?yàn)榈谝粋€(gè)日程安排并不包含時(shí)間 20 。
說明:
每個(gè)測(cè)試用例淹接，調(diào)用 MyCalendar.book 函數(shù)最多不超過 1000次十性。
調(diào)用函數(shù) MyCalendar.book(start, end)時(shí)， start 和 end 的取值范圍為 [0, 10^9]塑悼。
思路:
- 有序列表
因?yàn)?start 和 end 的取值范圍為 [0, 10^9]
可以設(shè)置兩個(gè)哨兵 (-2, -1), (10 ** 9 + 1, 10 ** 9 + 2) 保證 start 和 end 在這個(gè)區(qū)間內(nèi)
每次使用二分查找查找插入的位置
判斷區(qū)間的位置及進(jìn)行合并操作
時(shí)間復(fù)雜度為 O(nlgn), 空間復(fù)雜度為 O(n) - 平衡二叉樹
用 C++ 中的 map 保證插入有序
每次使用二分查找查找插入的位置并判斷區(qū)間的位置
時(shí)間復(fù)雜度為 O(nlgn), 空間復(fù)雜度為 O(n)
代碼:
C++:
class MyCalendar
{
private:
map<int, int> data;
public:
MyCalendar() {}
bool book(int start, int end)
{
auto it = data.lower_bound(end);
if (it != data.begin() and (--it) -> second > start) return false;
data[start] = end;
return true;
}
};
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar* obj = new MyCalendar();
* bool param_1 = obj->book(start,end);
*/
Java:
class MyCalendar {
private List<int[]> data;
public MyCalendar() {
data = new ArrayList<int[]>();
data.add(new int[]{ -2, -1 });
data.add(new int[]{ 1000000001, 1000000002 });
}
public boolean book(int start, int end) {
int l = 0, r = data.size() - 1;
while (l < r) {
int mid = l + ((r - l) >> 1);
if (start > data.get(mid)[0]) l = mid + 1;
else r = mid;
}
if (start >= data.get(l - 1)[1] && end <= data.get(l)[0]) {
data.add(l, new int[]{ start, end });
return true;
}
return false;
}
}
/**
* Your MyCalendar object will be instantiated and called as such:
* MyCalendar obj = new MyCalendar();
* boolean param_1 = obj.book(start,end);
*/
Python:
class MyCalendar:
def __init__(self):
self.data = [(-2, -1), (10 ** 9 + 1, 10 ** 9 + 2)]
def book(self, start: int, end: int) -> bool:
l, r = 0, len(self.data) - 1
while l < r:
mid = l + ((r - l) >> 1)
if start > self.data[mid][0]:
l = mid + 1
else:
r = mid
if start >= self.data[l - 1][1] and end <= self.data[l][0]:
self.data.insert(l, (start, end))
return True
return False
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(start,end)
