LWC 59:729. My Calendar I

LWC 59:729. My Calendar I

传送门:729. My Calendar I

Problem:

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking. Your class will have the 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 double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.) For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double 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(15, 25); // returns false MyCalendar.book(20, 30); // returns true Explanation: The first event can be booked. The second can’t because time 15 is already booked by another event. The third event can be booked, as the first event takes every time less than 20, but not including 20.

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情况或者B情况中,所以不需要重复判断。

代码如下:

class MyCalendar {

    class Interval{
        int s;
        int e;

        Interval(int s, int e){
            this.s = s;
            this.e = e;
        }
    }

    List<Interval> mem;

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

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

    public boolean overlap(Interval cand) {
        for (Interval tmp : mem) {
            if (overlap(tmp, cand)) return true;
        }
        return false;
    }

    boolean overlap(Interval a, Interval b) {
        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) {
            return true;
        }
        return false;
    }
}     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

中文分词组件:thulac及jieba试用手记

THULAC由《清华大学自然语言处理与社会人文计算实验室》研制推出的一套中文词法分析工具包。 官网地址:http://thulac.thunlp.org,该项目...

382
来自专栏Winter漫聊技术

一个随机播放的算法II

音乐时光? 骑着车,戴着耳机,播放列表里有几首歌。 突然,很想听《且听风吟》,但是不想掏出手机,于是一路双击耳机播放键切歌。 emmm,下面是切过的歌:

753
来自专栏深度学习之tensorflow实战篇

R语言之系统聚类(层次)分析之图谱形式完整版

读取数据常见错误: 在读取数据过程中可能遇到以下问题,参照上一篇博客: 可能遇到报错: 1、Error in if (is.na(n) || n > 65536...

4115
来自专栏安富莱嵌入式技术分享

【安富莱专题教程第1期】基于STM32的硬件RGB888接口实现emWin的快速刷新方案,32位色或24

说明: 1. 首先感谢ST终于推出了ARGB格式的emWin库,可谓千呼万唤始出来,使用STM32的硬件RGB888接口刷新图片慢的问题终于得到解决。 2. 这...

581
来自专栏信安之路

Pin-in-CTF 学习整理记录

这次打 qctf,做到了一个 ollvm,控制流平坦化的题,虽然不是很明白原理(但这么叫感觉很 6 批)。听师傅们说可以用 pin 解决,于是先学习一下 pin...

980
来自专栏歪先生_自留地

Python test2

823
来自专栏王磊的博客

Xamarin开发笔记—百度在线语音合成

续《是时候开始用C#快速开发移动应用了》刷屏之后,把C#开发移动应用的技术 => Xamarin,在这里和大家做一个分享! 语音合成:也被称为文本转换技术(TT...

2485
来自专栏黑白安全

如何攻破加密算法

当应用加密算法时,有许多地方可能会出错。难点在于识别和分析程序员用来加密的方法,然后寻找其中的漏洞。漏洞的种类也很多,比如弱加密算法、弱密钥生成器、服务端漏洞和...

682
来自专栏Y大宽

ChIP-seq详细分析流程

参考生信技能树1以及生信技能树2 只记录从数据下载,到最终结果展示,具体生物学知识请自行查阅 稍后关于ChIP-seq的背景知识我会再发布一篇文章。 数据...

531
来自专栏前端架构

javascript计算昨天yesterday明天tomorrow后天after tomorrow的方法

javascript计算昨天yesterday明天tomorrow后天after tomorrow的方法呢

745

扫码关注云+社区