algo-aha

要维护区间集合，区间按起点排

插入新区间

• https://leetcode.com/problems/insert-interval/

vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
    // 区间互不重叠、已按起点排序
    vector<vector<int>> before, after; // 前后的不重叠区间
    int left = newInterval[0], right = newInterval[1];
    for (auto& interval : intervals) {
        if (interval[1] < left) before.push_back(interval);
        else if (interval[0] > right) after.push_back(interval);
        else {
            left = min(left, interval[0]);
            right = max(right, interval[1]);
        }
    }

    before.push_back({left, right});
    before.insert(end(before), begin(after), end(after));
    return before;
}

合并区间列表

• https://leetcode.com/problems/merge-intervals/

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};
    sort(begin(intervals), end(intervals));
    
    vector<vector<int>> ans;
    for (auto &interval : intervals) {
        if (ans.empty() || interval[0] > ans.back()[1]) {
            ans.push_back(interval);
        } else {
            ans.back()[1] = max(ans.back()[1], interval[1]);
        }
    }
    return ans;
}

区间数组合并后的总长

• https://leetcode.com/problems/rectangle-area-ii/ 一部分

int getWidth(multiset<vector<int>> &st) {
    int ans = 0;
    int curr = INT_MIN;
    // curr往右扩展，只累加变长的部分
    for (auto &x : st) {
        curr = max(curr, x[0]);
        ans += max(x[1] - curr, 0);
        curr = max(curr, x[1]);
    }
    return ans;
}

或者同上题写法

维护区间集合

• https://leetcode.com/problems/data-stream-as-disjoint-intervals/
• https://leetcode.com/problems/range-module

class RangeModule {
    map<int, int> _ranges; // left=>right, [left,right)
    using RI = map<int, int>::iterator;
    array<RI, 2> getOverlapRanges(int left, int right) {
        // 在端点重合处，认为重叠
        // 左边找第一个相交的区间
        auto l = _ranges.upper_bound(left); // toFind.left>left
        if (l != begin(_ranges) && prev(l)->second >= left) // toFind.left<=left&&toFind.right>=left
            l = prev(l);
        // 右边找第一个不相交的区间
        auto r = _ranges.upper_bound(right); // toFind.left>right
        return {l, r};
    }
public:
    RangeModule() { 
    }
    
    void addRange(int left, int right) {
        auto [l, r] = getOverlapRanges(left, right);
        if (l != r) {
            left = min(left, l->first);
            right = max(right, prev(r)->second);
            _ranges.erase(l, r);
        }
        _ranges[left] = right;
    }
    
    bool queryRange(int left, int right) {
        auto [l, r] = getOverlapRanges(left, right);
        return l != r && l->first <= left && right <= l->second;
    }
    
    void removeRange(int left, int right) {
        auto [l, r] = getOverlapRanges(left, right);
        if (l != r) {
            int lower = min(left, l->first);
            int upper = max(right, prev(r)->second);
            _ranges.erase(l, r);
            if (lower < left) _ranges[lower] = left;
            if (right < upper) _ranges[right] = upper;
        }
    }
};

俄罗斯方块落下后的最大高度

• https://leetcode.com/problems/falling-squares/

class Solution {
    // left=>[right,height], [left,right)
    map<int, array<int, 2>> _ranges;
    using RI = map<int, array<int, 2>>::iterator;
    array<RI, 2> getOverlapRanges(int left, int right) {
        // 在端点重合处，不认为重叠
        auto l = _ranges.upper_bound(left); // toFind.left>left
        if (l != begin(_ranges) && prev(l)->second[0] > left) // toFind.left<=left&&toFind.right>left
            l = prev(l);
        auto r = _ranges.lower_bound(right); // toFind.left>=right
        return {l, r};
    }
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        vector<int> ans;
        int highest = 0;
        for (auto &pos : positions) {
            int left = pos[0], right = pos[0] + pos[1], height = pos[1];
            auto [l, r] = getOverlapRanges(left, right);
            if (l != r) {
                // 重叠区间的最大高度是新块儿的放置高度
                int baseH = 0;
                for (auto i = l; i != r; i++) {
                    baseH = max(baseH, i->second[1]);
                }
                height += baseH;
                // 删除重叠区间
                int lower = min(left, l->first), lH = l->second[1];
                int upper = max(right, prev(r)->second[0]), rH = prev(r)->second[1];
                _ranges.erase(l, r);
                if (lower < left) _ranges[lower] = {left, lH};
                if (right < upper) _ranges[right] = {upper, rH};
            }
            _ranges[left] = {right, height};

            highest = max(highest, height);
            ans.push_back(highest);
        }
        return ans;
    }
};