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

相关文章

来自专栏云端漫步

go设计模式之建造者模式

func NewBuilder(build Builder) *Director {

593
来自专栏专注研发

poj-1503-java大数相加

One of the first users of BIT's new supercomputer was Chip Diller. He extended h...

611
来自专栏机器学习入门

挑战程序竞赛系列(72):4.7高度数组(2)

挑战程序竞赛系列(72):4.7高度数组(2) 传送门:POJ 3415: Common Substrings 题意: 公共子串:统计A和B长度不小于K的公共...

17910
来自专栏机器学习入门

POJ 刷题系列:1503 Integer Inquiry

POJ 刷题系列:1503 Integer Inquiry 传送门:POJ 1503 Integer Inquiry 题意: 实现VeryLongIntege...

1957
来自专栏Jed的技术阶梯

Java设计模式之工厂方法模式

女娲补天的故事大家都听说过吧,今天不说这个,说女娲创造人的故事,可不是“造人”的工作,这个词被现代人滥用了。这个故事是说,女娲在补了天后,下到凡间一看,哇塞,风...

1042
来自专栏机器学习入门

LWC 58:726. Number of Atoms

LWC 58:726. Number of Atoms 传送门:726. Number of Atoms Problem: Given a chemical ...

2135
来自专栏机器学习入门

LWC 51:681. Next Closest Time

LWC 51:681. Next Closest Time 传送门:681. Next Closest Time Problem: Given a time ...

2366
来自专栏跟着阿笨一起玩NET

LINQ to JavaScript

JSLINQ 是一个将LINQ对象转化为JavaScript对象的工具 。它是构建在JavaScript的数组对象的基础上进行转换的,如果您使用的是一个数组,你...

622
来自专栏极乐技术社区

小程序摄像头使用技巧

1332
来自专栏Hongten

java web开发_购物车数据封装及数据展示

现在大家有没有明白我要说的是什么东东?如果还是不太明白,那么我就用最简单的语句描述一下:

651

扫码关注云+社区