L 370. Range Addition ----------M ~~~~~第二种方法

Assume you have an array of length n initialized with all 0's and are given k update operations.

Each operation is represented as a triplet: [startIndex, endIndex, inc] which increments each element of subarray A[startIndex ... endIndex] (startIndex and endIndex inclusive) with inc.

Return the modified array after all k operations were executed.

Example:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Explanation:

Initial state:
[0,0,0,0,0]

After applying operation [1,3,2]:
[0,2,2,2,0]

After applying operation [2,4,3]:
[0,2,5,5,3]

After applying operation [0,2,-2]: 

[-2,0,3,5,3] 

A:

这个考虑到可能有多个重复区间，因此，我们不能简单地sort一下就够。

需要用heap , 每次去除最前面的两个interval, 然后对比并merge

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        auto compare = [](const vector<int> &a, const vector<int> &b){
            if(a[0]==b[0]){
                return a[1] > b[1];
            }else{
                return a[0] > b[0];
            }
        };
        priority_queue<vector<int>,vector<vector<int>>, decltype(compare)> minQ(compare);        
        for(auto & t : updates){
            minQ.push(t);
        }
        vector<int> res(length,0);
        while(not minQ.empty()){
            auto start = minQ.top(); //CANNOT use auto &, otherwise, start[] cannot be assigned
            minQ.pop();
            if(minQ.empty()){
                updateRange(res, start[0], start[1], start[2]);
                break;
            }
            auto end = minQ.top();
            minQ.pop();
            if(start[1] < end[0]){ // two disjoint set
                updateRange(res, start[0], start[1], start[2]);
                minQ.push(end);
            }else if( end[1] <= start[1]  ){
                updateRange(res, start[0], end[0]-1, start[2]);
                updateRange(res, end[0], end[1], start[2]+end[2]);
                start[0] = end[1]+1;
                minQ.push(start);
            }else{ // start[1] < end[1]                
                updateRange(res, start[0], end[0]-1, start[2]);
                updateRange(res, end[0], start[1], start[2] + end[2]);
                end[0] = start[1]+1;
                minQ.push(end);
            }
        }        
        return res;
    }
private:
    void updateRange(vector<int> & res, int start, int end, int val){
        for(int i =start; i<= end;i++){
            res[i] += val;
        }
    }
};

错误，就是一开始用了sort().  然而那样是不够的。

**********************方法二 ***********

很巧妙的方法，  每次在interval的开始放上 增加的值。 并在结束位置的下一个，放上其相应的负值。    最终在结果上，从前往后加起来即可

class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        vector<int> res(length, 0);
        for(auto & t : updates){
            res[t[0]] += t[2];
            if(t[1]+1<length)
                res[t[1]+1] -= t[2];
        }
        for(int i =1;i<length;i++){
            res[i] += res[i-1];
        }
        return res;
    }
};