【C/C++】729. 我的日程安排表 I

---

题目链接：729. 我的日程安排表 I

题目描述

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

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

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

实现 MyCalendar 类：

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

提示:

• 0⩽start<end⩽1090 \leqslant start < end \leqslant 10^90⩽start<end⩽109
• 每个测试用例，调用 book 方法的次数最多不超过 1000 次。

示例 1：

输入：
["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 。

整理题意

题目给定多个左闭右开区间范围，要求我们对于每个区间范围进行操作和判断：

• 如果当前给定的区间范围与集合中的所有区间范围没有交集，就将该区间范围插入集合，并返回 true；
• 如果存在交集就不插入集合中，并返回 false。

需要注意给定的区间是 左闭右开 区间。

解题思路分析

该题和 715. Range 模块 很类似，并且难度低于该题，因为只需判断是否与集合中的区间范围有交集和插入集合两个操作。而 715. Range 模块 需要合并区间和删除区间等操作。

我们可以使用有序集合 map 进行存储区间范围，当然也可以使用有序的 set 集合进行存储。

对于每个给定的区间范围我们在集合中查找是否与集合中的区间范围有交集即可：

• 如果有交集直接返回 false
• 没有交集就将区间插入集合中，并返回 true

对于在集合中查找是否有交集时，因为我们使用的是有序集合，所以不用遍历集合中的所有集合，可以直接在有序集合中使用二分查找即可。

具体实现

1. 创建有序集合 map，令 key 为左端点，value 为右端点：map[start] = end；
2. 对于每个给定的区间范围，我们在集合中使用二分查找 第一个大于 该区间左端点的区间 iter，如果集合为空，我们可以直接插入该区间，并返回 true；
3. 我们令 iter 的前一个区间为 it（如果存在前一个区间的话），那么这样就可以保证 start 在 it 和 iter 之间： it->first <= start < iter->first。
4. 首先判断 start 是否与前一个区间有交集（如果存在前一个区间的话），如果当前 iter 为 mp.begin() 的话说明没有前一个区间，可以跳过该判断步骤。
5. 再判断 end 是否与后一个区间有交集（如果存在后一个区间的话），如果当前 iter 为 mp.end() 的话说明没有后一个区间，可以跳过该判断步骤。
6. 最终确定给定区间范围是否与集合中的区间有交集，如果有交集返回 false，否则将该区间插入集合中，并返回 true。

需要注意判断当前给定区间与集合中区间位置的各种情况，包括是否存在前后区间，与集合中区间是否存在交集。

复杂度分析

• 时间复杂度：O(nlog⁡n)O(n \log n)O(nlogn), 其中 n 表示日程安排的数量。由于每次在进行预订时，都需要进行二分查找，需要的时间为 O(log⁡n)O(\log n)O(logn)。
• 空间复杂度：O(n)O(n)O(n)，其中 n 表示日程安排的数量。需要保存所有已经预订的行程。

代码实现

class MyCalendar {
private:
    //mp[start] = end;
    map<int, int> mp;
public:
    MyCalendar() {
        mp.clear();
    }
    
    bool book(int start, int end) {
        //当集合为空时直接插入
        if(mp.size() == 0){
            mp[start] = end;
            return true;
        }
        auto iter = mp.upper_bound(start);
        //判断是否在第一个集合之前
        if(iter == mp.begin()){
            if(end <= iter->first){
                mp[start] = end;
                return true;
            }
            else return false;
        }
        else{
            //判断是否在前后两个集合之间没有交集的部分
            auto it = prev(iter);
            if(it->second > start) return false;
            if(iter != mp.end() && iter->first < end) return false;
            mp[start] = end;
            return true;
        }
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

总结

• 由于该题数据范围较小，O(n2)O(n^2)O(n2) 的暴力也是可以通过的，但是这样就失去了题目本身的意义了。同时本题还可以使用更为进阶的线段树进行解决，但由于其无实质上的复杂度提升，反而使得代码实现更为困难，所以不推荐。
• 在有序集合中使用二分查找的技巧，可以先查找第一个大于当前区间的节点，然后通过 prev() 找到上一个区间节点，这样就可以保证所要查找的区间一定在这两个区间之间，更容易分类讨论和处理。
• 该题本质上为 分类讨论 的题目，判断给定区间与集合中区间位置的各种情况并进行分类讨论和处理。
• 测试结果：

结束语

成绩的获得不是解决，而恰恰意味着下一段努力的开始。只有那些始终渴望着向着更高层次攀登，并且愿意脚踏实地地为之付出的人，才能够最大限度释放自己的潜力。这段一往无前的历程，就是有滋有味的人生。新的一天，加油！