LC1893.检查是否区域内所有整数都被覆盖

思路

• 每个遍历到的区间，区间内部元素全部+ 1（利用差分，可以在O(1)时间内实现）
• 如果[left, right]区间内依然存在0，说明没有被完全加上，说明没有完全覆盖，否则说明已经完全覆盖。

• 差分依然要有“公交车上车下车”的实际联想。

  代码

  class Solution {
  public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        // 起始为0
        // 遇到一个区间，区间内部所有的数值 + 1
        // 最后查区间内部是不是都是0即可
        vector<int> full_range(50 + 5, 0);
        vector<int> diff(50 + 5, 0);
        for (int i = 0, n = ranges.size(); i < n; ++i) {
            int begin_pos = ranges[i][0];
            int end_pos = ranges[i][1];
            diff[begin_pos] += 1;
            diff[end_pos + 1] -= 1;
        }
        for (int i = 0; i < 50 + 5; i++) {
            if (i == 0) {
                full_range[0] = diff[0];
            } else {
                full_range[i] = full_range[i - 1] + diff[i];
            }
        }
        for (int i = left; i <= right; i++) {
            if (full_range[i] == 0) {
                return false;
            }
        }
        return true;
    }
  };