原文链接: https://leetcode-cn.com/problems/my-calendar-i

英文原文

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking.

A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendar class:

• MyCalendar() Initializes the calendar object.
• boolean book(int start, int end) Returns 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.

 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.

 

Constraints:

• 0 <= start < end <= 109
• At most 1000 calls will be made to book.

中文题目

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ，则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生 重复预订 。

日程可以用一对整数 start 和 end 表示，这里的时间是半开区间，即 [start, end), 实数 x 的范围为，  start <= x < end 。

实现 MyCalendar 类：

• MyCalendar() 初始化日历对象。
• boolean book(int start, int end) 如果可以将日程安排成功添加到日历中而不会导致重复预订，返回 true 。否则，返回 false 并且不要将该日程安排添加到日历中。

 

示例：

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

解释：
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ，这个日程安排不能添加到日历中，因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ，这个日程安排可以添加到日历中，因为第一个日程安排预订的每个时间都小于 20 ，且不包含时间 20 。

 

提示：

• 0 <= start < end <= 109
• 每个测试用例，调用 book 方法的次数最多不超过 1000 次。

通过代码

官方题解

方法一：暴力法

预订新的日程安排 [start, end) 时，检查当前每个日程安排是否与新日程安排冲突。若不冲突，则可以添加新的日程安排。

算法：
我们将维护一个日程安排列表（不一定要排序）。当且仅当其中一个日程安排在另一个日程安排结束后开始时，两个日程安排 [s1，e1) 和 [s2，e2) 不冲突：e1<=s2 或 e2<=s1。这意味着当 s1<e2 和 s2<e1 时，日程安排发生冲突。

[ ]
class MyCalendar(object):
    def __init__(self):
        self.calendar = []

    def book(self, start, end):
        for s, e in self.calendar:
            if s < end and start < e:
                return False
        self.calendar.append((start, end))
        return True

[ ]
public class MyCalendar {
    List<int[]> calendar;

    MyCalendar() {
        calendar = new ArrayList();
    }

    public boolean book(int start, int end) {
        for (int[] iv: calendar) {
            if (iv[0] < end && start < iv[1]) return false;
        }
        calendar.add(new int[]{start, end});
        return true;
    }
}

复杂度分析

• 时间复杂度：$O(N^2)$。$N$ 指的是日常安排的数量，对于每个新的日常安排，我们检查新的日常安排是否发生冲突来决定是否可以预订新的日常安排。所以时间复杂度为 $\sum_k^N O(k) = O(N^2)$。
• 空间复杂度：$O(n)$，calendar 所使用的空间大小。

方法二：平衡树

如果我们按时间顺序维护日程安排，则可以通过二分查找日程安排的情况来检查新日常安排是否可以预订，时间复杂度为 $O(\log N)$ （其中 $N$ 是已预订的日常安排数），若可以预定则我们还需要在排序结构中插入日常安排。

算法：

• 我们需要一个数据结构能够保持元素排序和支持快速插入。在 java 中，TreeMap 是最适合的。在 python 中，我们可以构建自己的二叉树结构。

[ ]
class Node:
    __slots__ = 'start', 'end', 'left', 'right'
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.left = self.right = None

    def insert(self, node):
        if node.start >= self.end:
            if not self.right:
                self.right = node
                return True
            return self.right.insert(node)
        elif node.end <= self.start:
            if not self.left:
                self.left = node
                return True
            return self.left.insert(node)
        else:
            return False

class MyCalendar(object):
    def __init__(self):
        self.root = None

    def book(self, start, end):
        if self.root is None:
            self.root = Node(start, end)
            return True
        return self.root.insert(Node(start, end))

[ ]
class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start),
                next = calendar.ceilingKey(start);
        if ((prev == null || calendar.get(prev) <= start) &&
                (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

复杂度分析

• 时间复杂度 (Java)：$O(N \log N)$。其中 $N$ 是预订的日程安排数。对于每个新日程安排，我们用 $O(\log N)$ 的时间搜索该日程安排是否合法，若合法则将其插入日常安排中需要 $O(1)$ 的时间。
• 时间复杂度 (Python)：最坏的情况 $O(N^2)$，其他情况是 $O(N \log N)$。对于每个新日程安排，若新日程安排合法则将新日程安排插入到二叉树中。由于此树可能不平衡，因此可能需要线性步骤来遍历每个日常安排。
• 空间复杂度：$O(N)$，数据结构所使用的空间。

统计信息

通过次数	提交次数	AC比率
9232	17844	51.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
我的日程安排表 II	中等
我的日程安排表 III	困难