LWC 59:731. My Calendar II

LWC 59:731. My Calendar II

传送门:729. 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].

思路: 水过,当新加入一个区间时,如果在该区间内,出现重复的区间时,则认为是a triple booking,关键在于如何求出两个区间的重叠区间,画个图就能明白,重叠区间为:

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

首先排除一部分冗余区间,左侧的与候选区间的不重叠区间和右侧的不重叠区间均可以排除,而中间那一部分,则需要以O(n2)O(n^2)的时间复杂度来计算每两个区间的重叠区域,是否与候选区域发生重叠。

代码如下:

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 {
            mem.add(candicate);
            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;
    }
}

再来一种积分的思路,时间复杂度为O(n2)O(n^2),加入新的区间后,判断当前区间的累积值是否超过3,超过3则说明该区间不该被加入,重新去除。

具体查看imos 累积法

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 条评论
登录 后参与评论

相关文章

来自专栏静晴轩

精妙JS代码段搜集

现在到处都是JavaScript,倘若花点时间去体察,每次都能知道点新的东西。一旦你入了门,你总能从这里或是那里领悟到很多知识。一旦发现些许有意思的东西,总习惯...

3325
来自专栏专注 Java 基础分享

Java ---自定义标签(二)

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

1937
来自专栏游戏杂谈

关于AS3的事件移除释疑

as3.0中的事件Event(位于包flash.events内,继承至Object,子类有…)

852
来自专栏hightopo

HT for Web基于HTML5的图像操作(二)

1242
来自专栏向治洪

React 之props属性

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

2075
来自专栏图形学与OpenGL

CG实验6 交互与动画

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

971
来自专栏HTML5学堂

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

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

2705
来自专栏大数据钻研

前端编码规范

基本原则 结构、样式、行为分离 统一缩进(建议 两个空格) 文件编码统一 不带BOM的UTF-8 一律使用小写字母 省略外链资源 URL 协议部分(FTP等其他...

3197
来自专栏偏前端工程师的驿站

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

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

943
来自专栏前端说吧

百度前端学院js课堂作业合集+分析(更新中...)

4459

扫码关注云+社区