715. Range Module

https://leetcode.com/problems/range-module/description/

给定一系列interval，实现对它们的添加，查询(给定Interval是否完全包括在已有内)和删除。在对interval操作后把有重叠的合并并保证interval有序后，查询直接二分定位到和input 有overlap的那个interval。同样添加和删除也是在查询到overlap interval后做合并，添加是合并后把合并的插入，删除是把overlap都删除，再补上两端可能多删的。查询overlap参考了花花的实现，非常精妙。根据[left, right]查overlap得到两个interval iterator l和r, 保证[left,right]一定在[l,r)内。这样当l == r时说明[left, right]和已有Intervals无交集。

/*
 * @lc app=leetcode id=715 lang=cpp
 *
 * [715] Range Module
 */

// @lc code=start
class RangeModule {
public:
    map<int, int> ranges;
    typedef map<int, int>::iterator IT;
    inline void overlapRanges(const int left, const int right, IT &l, IT &r) {
        // interval中第一个比left和right大的start
        l = ranges.upper_bound(left);
        r = ranges.upper_bound(right);
        // [left, right] 一定在[l, r)内
        if (l != ranges.begin()) {
            if (prev(l)->second >= left) {
                --l;
            }
        }
    }

    RangeModule() {}
    
    void addRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        if (l != r) {
            auto last = r;
            --last;
            left = min(left, l->first);
            right = max(right, last->second);
            ranges.erase(l, r);
        }
        ranges[left] = right;
    }
    
    bool queryRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        // 左闭右开，相等说明无overlap.
        if (l == r) return false;
        // 是否全部包含在了l里。
        return l->first <= left && l->second >= right;
    }
    
    void removeRange(int left, int right) {
        IT l, r;
        overlapRanges(left, right, l, r);
        if (l == r) return;
        auto last = r;
        --last;
        int start = min(left, l->first);
        int end = max(right, last->second);
        // 删掉所有overlap的ranges
        ranges.erase(l, r);
        // 补上可能多删掉的
        if (start < left) ranges[start] = left;
        if (end > right) ranges[right] = end;
    }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */
// @lc code=end