Skip to content

715. Range Module

715. Range Module

题目: https://leetcode.com/problems/range-module/

难度: Hard

题意：

  1. 设计一种数据结构
  2. 操作1：向该数据结构插入一个线段（的所有实数）
  3. 操作2：向该数据结构删除一个线段（的所有实数）
  4. 操作3：查询一个线段包含的所有实数是否都在这个数据结构中

思路：

  • 线段与线段之间有三种关系，包含，相交，相离。插入一个线段，我们需要寻找可能包含和相交的线段来合并
  • 假设插入的线段为[a,b)，我们需要在已有的线段中寻找包含和相交的线段。假设已有线段为[i,j)，当j b
  • 我们需要一种数据结构，可以遍历，可以快速定位到比某个数小的最大值。平衡树满足我们的需求。
  • 平衡树的key是线段的左端点，value是线段的右端点
  • 剩下的操作就是线段合并和线段删除了，用笔模拟一下就可以得到结果

解法：

class RangeModule {
public:
    map<int, int> range;
    RangeModule() {

    }

    struct Range {
        int x, y;
        Range(int _x = 0, int _y = 0) : x(_x), y(_y) {}
    };

    int min(int a, int b) {
        return a < b ? a : b;
    }

    int max(int a, int b) {
        return a < b ? b : a;
    }

    void addRange(int left, int right) {
        if (range.size() == 0) {
            range[left] = right;
            return;
        }
        map<int, int>::iterator it;
        vector<int> forDelete;
        it = range.upper_bound(left);
        if (it != range.begin()) {
            it--;
        }
        while (it != range.end() && it->first <= right) {
            if ((it -> second >= right && it -> first <= right) || (right >= it -> second && left <= it -> second)) {
                forDelete.push_back(it -> first);
                left = min(left, it -> first);
                right = max(right, it -> second);
            }
            it++;
        }
        for (int i = 0;i < forDelete.size();i++) {
            range.erase(forDelete[i]);
        }
        range[left] = right;
    }

    bool queryRange(int left, int right) {
        if (range.size() == 0) {
            return false;
        }
        map<int, int>::iterator it;
        it = range.upper_bound(left);
        if (it != range.begin()) {
            it--;
        }
        if (it -> first <= left && it -> second >= right) {
            return true;
        } else {
            return false;
        }
    }

    void removeRange(int left, int right) {
        if (range.size() == 0) {
            return;
        }
        map<int, int>::iterator it;
        vector<int> forDelete;
        vector<Range> forInsert;
        it = range.upper_bound(left);
            if (it != range.begin()) {
            it--;
        }
        while (it != range.end() && it->first <= right) {
            if (it -> first >= left && it -> second <= right) {
                forDelete.push_back(it->first);
            } else if (it -> first < left && it -> second > right) {
                forDelete.push_back(it->first);
                forInsert.push_back(Range(it -> first, left));
                forInsert.push_back(Range(right, it -> second));
            } else if(it -> first < left && it -> second >= left) {
                forDelete.push_back(it->first);
                forInsert.push_back(Range(it -> first, left));
            } else if (it -> first <= right && it -> second > right) {
                forDelete.push_back(it->first);
                forInsert.push_back(Range(right, it -> second));
            } 
            it++;
        }
        for (int i = 0;i < forDelete.size();i++) {
            range.erase(forDelete[i]);
        }
        for (int i = 0;i < forInsert.size();i++) {
            range[forInsert[i].x] = forInsert[i].y;
        }
    }
};
回到顶部