题解 | #合并区间#

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param intervals Interval类vector
     * @return Interval类vector
     */
    vector<Interval> merge(vector<Interval>& intervals) {
        // write code here
        const int MAX_VAL = 2 * 1e5 * 2; // *2 处理整数区间连续的问题
        // 整数区间连续但不重叠，例如 [[1,4],[0,0]] 这个作为输入，[0,1] 这一段是不算在内的
        std::vector<int> line(MAX_VAL + 2, 0); // +2 处理边界情况

        for (const auto& interval : intervals) {
            line[interval.start * 2]++;
            // 问题就在下面这里，如果直接差分数组会在下一个整数这里设置上标志，
            // 连续但不重叠区间的话 -1 + 1 = 0，标志消失了。
            // 我们本来是利用这个标志的，结果这里被标志拖累了。
            // 如果乘以 2，在下一个整数这里 -1 不会影响到真正的下一个整数
            line[interval.end * 2 + 1]--;
        }

        std::vector<Interval> merged;
        int current = 0;
        int start = -1;

        for (int i = 0; i <= MAX_VAL; ++i) {
            int previous = current;
            // cout << "previous = " << previous << endl;
            current += line[i];
            // cout << "current = " << current << endl;
            if (current > 0 && start == -1) {
                start = i;
            } else if (current == 0 && previous > 0) {
                merged.emplace_back(start, i - 1);
                start = -1;
            }
        }

        for (auto& interval : merged) {
            interval.start /= 2;
            interval.end /= 2;
        }

        return merged;
    }
};