2158. Amount of New Area Painted Each Day

There is a long and thin painting that can be represented by a number line. You are given a 0-indexed 2D integer array paint of length n, where paint[i] = [starti, endi]. This means that on the ith day you need to paint the area between starti and endi.

Painting the same area multiple times will create an uneven painting so you only want to paint each area of the painting at most once.

Return an integer array worklog of length n, where worklog[i] is the amount of new area that you painted on the ith day.

• new solution update 2022.05.14

c++

class Solution {
    map<int, int> interval;
    map<int,int>::iterator front(int s) {
        auto it = interval.upper_bound(s);
        if(it == begin(interval)) {
            return interval.insert({s,s}).first;
        }
        --it;
        if(it->second >= s)
            return it;
        return interval.insert({s,s}).first;
    }
    int merge(int s, int e) {
        int res = 0;
        auto it = front(s);
        while(it->second < e) {
            auto nxt = next(it);
            if(nxt != end(interval) and nxt->first <= e) {
                res += nxt->first - it->second;
                it->second = nxt->second;
                interval.erase(nxt);
            } else {
                res += e - it->second;
                it->second = e;
            }
        }
        
        return res;
    }
public:
    vector<int> amountPainted(vector<vector<int>>& paint) {
        vector<int> res;
        for(auto& p : paint) {
            int s = p[0], e = p[1];
            res.push_back(merge(s,e));
        }
        
        return res;
    }
};

c++

class Solution {
    map<int, int> range;
    map<int,int>::iterator getStart(int from) {
        auto res = range.upper_bound(from);

        if(res != range.begin() and prev(res)->second >= from)
            return prev(res);
        return res;
    }
    int merge(int from, int to) {
        auto start = getStart(from);
        if(start == end(range)) {
            range[from] = to;
            return to - from;
        }
        if(start->first > to) {
            range[from] = to;
            return to - from;
        }
        int res = 0;
        auto nxt = next(start);
        while(nxt != end(range) and nxt->first <= to) {
            res += nxt->first - start->second;
            start->second = nxt->second;
            range.erase(nxt);
            nxt = next(start);
        }
        
        if(start->second < to) {
            res += to - start->second;
            start->second = to;
        }
        if(start->first > from) {
            res += start->first - from;
            range[from] = start->second;
            range.erase(start);
        }
        
        return res;
    }
public:
    vector<int> amountPainted(vector<vector<int>>& paint) {
       vector<int> res;
        for(auto p : paint) {
            res.push_back(merge(p[0], p[1]));
        }
        return res;
    }
};