设计类构造函数不懂class MyCalendar {
private:
vector<vector<int>> timeSlots;
public:
MyCalendar() {
}
bool book(int start, int end) {
if(timeSlots.size() == 0){
vector<int> times{start, end};
timeSlots.push_back(times);
return true;
}
for(int i = 0; i < timeSlots.size(); i++){
if(!(start >= timeSlots[i][1] || end <= timeSlots[i][0])){
return false;
}
}
vector<int> times{start, end};
timeSlots.push_back(times);
return true;
}
};
1/30/2019更新
/*方法二:(构造特殊的二叉搜索树 (https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855?fr=aladdin))
1. 类似在常见的二叉搜索树中查找某个数一样,如果我们能够实现出一种特殊的二叉搜索树,使得:
1. 树中每个节点是已加的一个时间段。
2. 能方便地查找新时间段与树中节点是否重叠。
2. 这样就能大幅提高效率。庆幸的是,这种想法是可行的。
3. 具体地,从树根开始搜索,当前搜索节点指向树根。新的时间段与当前节点有三种可能:
1. 完全在当前节点左侧,则当前节点指向左孩子;
2. 完全在当前节点右侧,则当前节点指向右孩子;
3. 有重叠,直接返回false。
4. 循环该过程,直到当前节点指空。指空说明新的时间段与整棵树无重叠,则把新的时间段添加在当前位置,并返回true。
6. 复杂度分析:
1. 时间复杂度:O(N * logN),N是添加成功的时间段数量,对于每一个时间段的搜索需要O(logN),添加需要O(1)。(*注意:*这里的O(N * logN)只能看作是平均时间复杂度,因为搜索最坏需要O(N)。 如果在手动构造二叉搜索树时实现了平衡处理或者使用了TreeMap等标准库,可保证O(N * logN)仍为最坏时间复杂度)
2. 空间复杂度O(N),用于构造二叉树。
*/
class Node {
private:
int start, end;
Node * left, * right;
public:
Node(int start, int end) {
this->start = start;
this->end = end;
this->left = this->right = NULL;
}
bool insert(Node * node) {
if (node->start >= this->end) {
if (!this->right) {
this->right = node;
return true;
}
return this->right->insert(node);
}
else if (node->end <= this->start) {
if (!this->left) {
this->left = node;
return true;
}
return this->left->insert(node);
}
else {
return false;
}
}
};
class MyCalendar {
private:
Node * root;
public:
MyCalendar() {
this->root = NULL;
}
bool book(int start, int end) {
if (this->root) {
return this->root->insert(new Node(start, end));
}
this->root = new Node(start, end);
return true;
}
};
Comments
Post a Comment