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

相关文章

来自专栏Jack-Cui

Day4、Python

题目     一个数如果恰好等于它的因子之和,这个数就成为“完数”。例如6=1+2+3。编程找出1000以内的所有完数。 程序分析     完全数(...

1810
来自专栏吉浦迅科技

DAY36:阅读”执行空间&扩展修饰符

1113
来自专栏Python中文社区

Python优化第一步: 性能分析实践

專 欄 ❈Pytlab,Python中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,蒙...

20210
来自专栏WD学习记录

牛客网 不用加减乘除做加法

看到题目,最直接的想法应该是按照二进制的计算,然而看到好多人提交的是用sum()函数。

674
来自专栏聊聊技术

原 2015 Multi-Universi

33012
来自专栏数据结构与算法

洛谷P1976 鸡蛋饼

题目背景 Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问,小 x 道出 了实情:因为他喜欢圆。 题目描述 最近小 x 又发现了一个关于...

3225
来自专栏数据结构与算法

3022 西天收费站

题目描述 Description 唐僧师徒四人终于发现西天就在眼前,但猴子突然发现前面有n个收费站(如来佛太可恶),在每个收费站用不同的方式要交的钱不同,输入每...

2525
来自专栏恰同学骚年

设计模式的征途—8.桥接(Bridge)模式

在现实生活中,我们常常会用到两种或多种类型的笔,比如毛笔和蜡笔。假设我们需要大、中、小三种类型的画笔来绘制12中不同的颜色,如果我们使用蜡笔,需要准备3*12=...

903
来自专栏数据结构与算法

2570 绝对素数

2570 绝对素数 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一个自然数...

3157
来自专栏恰同学骚年

剑指Offer面试题:29.丑数

  使用遍历法求第k个丑数,从1开始遍历,如果是丑数则count++,直到count=k为止。那么如何判断丑数呢?根据丑数的定义,丑数只有2,3,5这三个因子,...

642

扫码关注云+社区