# Halo

A magic place for coding

0%

## 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)

Example1:

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].

## Analysis

这是Calendar系列的第二题，题目要求我们判断会议是否三重重叠。也就是说，没有重叠和两个会议重叠都是允许的，三个会议重叠则不允许。如果完成了[Calendar Ⅰ](http://leungyukshing.cn/archives/LeetCode解题报告（四）-- 729. My Calendar I.html)，这题会比较简单。判断重叠的条件与之前一样，关键在于需要记录不重叠区间和两个会议重叠的区间。

## Solution

我们需要两个vector来模拟一个分级的集合，分别记录不重叠的区间和一次重叠的区间。对于每个需要判断的区间，我们首先在一次重叠的vector中进行对比，如果存在交集，则说明出现了三个会议重叠的情况，直接return false；否则，从无重叠的区间中对比，如果存在重叠，则将重叠的区间加入到一次重叠的vector中，否则，直接把区间加入到不重叠的vector中。需要注意，两个区间的重叠区间是左边界取大，右边界取小

## Summary

这道题运用了一个分级的思想，将重叠程度不同的区间分集合存储，关键点是提取出重叠的区间加入下一级的vector。分析清楚后，其实coding过程没有什么坑。个人建议大家在动手之前还是在纸上写一下大概的思路，这样会高效很多。这道题的分享就到这里，谢谢！

Welcome to my other publishing channels