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 条评论

相关文章

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

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

2077

1748

2577

《HTML5实战》Lesson04

Week05    2016/10/12上午1-4节 一、复习 二、Javascirpt 1，html5中使用内部javascript <script>可以...

2834

关于AS3的事件移除释疑

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

942

2638

CG实验6 交互与动画

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

1111

1422

5019

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

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

2725