# LWC 59：731. My Calendar II

## LWC 59：731. My Calendar II

Problem:

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:

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].

```s = max(s1, s2), si = 区间i的开始坐标
e = min(e1, e2), ei = 区间i的结束坐标```

```class MyCalendarTwo {

class Interval implements Comparable<Interval>{
int s;
int e;
Interval(int s, int e){
this.s = s;
this.e = e;
}

@Override
public int compareTo(Interval o) {
return this.s == o.s ? this.e - o.e : this.s - o.s;
}

@Override
public String toString() {
return "[" + s + ", " + e +"]";
}
}

List<Interval> mem;

public MyCalendarTwo() {
mem = new ArrayList<>();
}

public boolean book(int start, int end) {
Interval candicate = new Interval(start, end);
if (tripleOverlap(candicate)) {
return false;
}
else {
return true;
}
}

boolean tripleOverlap(Interval candicate) {
Collections.sort(mem);
int n = mem.size();
int left = 0;
int right = n - 1;
while (left < n && candicate.s >= mem.get(left).e) left ++;
while (right >= 0 && candicate.e <= mem.get(right).s) right --;
for (int i = left; i <= right; ++i) {
for (int j = left; j < i; ++j){
Interval ans = new Interval(-1, -1);
if (overlap(mem.get(j), mem.get(i), ans)) {
if (overlap(ans, candicate, new Interval(-1, -1))) return true;
}
}
}
return false;
}

boolean overlap(Interval a, Interval b, Interval ans) {
if (b.s >= a.s && b.s < a.e || b.e <= a.e && b.e > a.s || b.s <= a.s && b.e >= a.e) {
ans.s = Math.max(b.s, a.s);
ans.e = Math.min(a.e, b.e);
return true;
}
return false;
}
}```

JAVA代码超时，C++则AC，代码如下：

```class MyCalendarTwo {
public:
map<int, int> m;
MyCalendarTwo() {
}

bool book(int start, int end) {
m[start] ++;
m[end] --;
int s = 0;
for (auto it : m) {
s += it.second;
if (s >= 3) {
m[end] ++;
m[start] --;
return false;
}
}
return true;
}
};```

0 条评论

## 相关文章

3325

### Java ---自定义标签（二）

上篇文章的最后，我们自定义了一个带属性的标签，并使用它完成了一个简单的案例。其实到这我们已经可以看出来，前端jsp页面只需要写一个类似html语法的标...

1937

### 关于AS3的事件移除释疑

as3.0中的事件Event（位于包flash.events内，继承至Object，子类有…）

852

1242

### React 之props属性

React 里有一个非常常用的模式就是对组件做一层抽象。组件对外公开一个简单的属性（Props）来实现功能，但内部细节可能有非常复杂的实现。 可以使用 JSX ...

2075

### CG实验6 交互与动画

(1) 示范代码1为交互实例：在鼠标点击的位置上绘制出点；示范代码2为动画实例：三角形按照恒定的速度（45度/秒）旋转。结合示范代码，学习理解交互与动画的基本思...

971

### 获取标签的那些事 之 动态集合

HTML5学堂：今天的内容从一道题开始，很简单，但是，你可能会“跪”得很惨。之后我们自然要挖一挖这个坑喽~所有学过JavaScript的人都知道获取标签，但是真...

2705

3197

### CSS魔法堂：一起玩透伪元素和Content属性

继上篇《CSS魔法堂：稍稍深入伪类选择器》记录完伪类后，我自然而然要向伪元素伸出“魔掌”的啦^_^。本文讲讲述伪元素以及功能强大的Contet属性，让我们可以...

943

4459