【leetcode】【剑指offer Ⅱ】058. 日程表

问题描述：

• 请实现一个 MyCalendar 类来存放日程安排。
  • 如果要添加的时间内没有其他安排，则可以存储这个新的日程安排。
  • MyCalendar 有一个 book(int start, int end) 方法。它意味着在 start 到 end 时间内增加一个日程安排，注意，这里的时间是半开区间，即 [start, end)。
  • 当两个日程安排有一些时间上的交叉时（例如两个日程安排都在同一时间内），就会产生重复预订。
  • 每次调用 MyCalendar.book 方法时，如果可以将日程安排成功添加到日历中而不会导致重复预订则返回 true，否则返回 false 并且不要将该日程安排添加到日历中。

核心思路：

• 该题和剑指 offer Ⅱ 057 值和下标之差都在给定的范围内的解题思路差不多，都是有序集合 + 二分搜索。
  • 具体来说，插入一个区间为 [start, end)，所以可以先对有序集合进行二分搜索（即调用 lower_bound）找到 [end, 0) 的第一个更大区间，此时判断该更大区间的前一个区间是否和 [start, end) 有重合即可。
  • 如果没有重合则将新区间插入到有序集合中。

代码实现：

class MyCalendar
{
private:
    set<pair<int, int>> ss;
public:
    MyCalendar() {}
    
    bool book(int start, int end)
    {
        auto iter = ss.lower_bound({end, 0});
        bool ans = false;
        if(iter == ss.begin() or (--iter)->second <= start) // iter前面没有区间 或者 iter前一个区间整体小于 [start, end)
        {
            ss.emplace(start, end);
            ans = true;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19