729. My Calendar I
Problem
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 startTime and endTime that represents a booking on the half-open interval [startTime, endTime), the range of real numbers x such that startTime <= x < endTime.
Implement the MyCalendar class:
MyCalendar()Initializes the calendar object.boolean book(int startTime, int endTime)Returnstrueif the event can be added to the calendar successfully without causing a double booking. Otherwise, returnfalseand do not add the event to the calendar.
https://leetcode.cn/problems/my-calendar-i/
Example 1:
Input
["MyCalendar", "book", "book", "book"][[], [10, 20], [15, 25], [20, 30]]
Output[null, true, false, true]
ExplanationMyCalendar 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 <= 10⁹- At most
1000calls will be made tobook.
Test Cases
class MyCalendar:
def __init__(self):
def book(self, startTime: int, endTime: int) -> bool:
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)import pytest
from solution import MyCalendar
null = None
false = False
true = True
@pytest.mark.parametrize('actions, params, expects', [
(
["MyCalendar", "book", "book", "book"],
[[], [10, 20], [15, 25], [20, 30]],
[null, true, false, true]
),
])
@pytest.mark.parametrize('clazz', [MyCalendar])
def test_solution(clazz, actions, params, expects):
sol = None
for action, args, expected in zip(actions, params, expects):
if action == 'MyCalendar':
sol = clazz(*args)
else:
assert getattr(sol, action)(*args) == expected
Thoughts
用一个数组记录所有已知的 events,且按开始时间排序。
对于想要 book 的一个 event,用二分搜索找到可以插入的位置。用 Python 的 bisect.bisect_left,返回的 i 满足 ∀events[:i] < event、∀events[i:] ≥ event。这时候只要检查 events[i-1] 是否在 event 之前结束、event 是否在 events[i] 之前结束。如果都符合,则可以将 event 插入到位置 i。
MyCalendar 构造的时间复杂度 O(1)。
book 方法的时间复杂度,当 book 失败的时候是 O(log n),book 成功的时候是 O(n)。如果用更高级的数据结构(比如有序集合、红黑树、AVL 等),可以做到 book 成功时也是 O(log n) 时间。
空间复杂度 O(n)。
Code
from bisect import bisect_left
class MyCalendar:
def __init__(self):
self._events: list[tuple[int, int]] = []
def book(self, startTime: int, endTime: int) -> bool:
i = bisect_left(self._events, (startTime, endTime)) # events[i] >= (startTime, endTime)
if i > 0: # events[i-1].start < startTime, need check events[i-1].end vs startTime.
if self._events[i-1][1] > startTime: return False
if i < len(self._events): # events[i].start >= startTime, need check events[i].start vs endTime.
if endTime > self._events[i][0]: return False
self._events.insert(i, (startTime, endTime))
return True
# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)
评论需要 JavaScript。