Different approach using operation merging


  • 0
    V

    Here we merge the updates which fall in same range. But this solution takes O(nlogn) time.

    class Solution {
    private:
        struct comparator {
            inline bool operator() (const vector<int>& a, vector<int>& b) {
                if (a[0] < b[0])
                    return true;
                else if (a[0] == b[0])
                    return a[1] < b[1];
                else
                    return false;
            }
        };
    public:
        vector<int> getModifiedArray(int n, vector<vector<int>>& u) {
            sort(u.begin(), u.end(), comparator());
            int i = 0;
            while (i < u.size()) {
                int j = i + 1;
                while (j < u.size() && u[i][0] == u[j][0] && u[i][1] == u[j][1])
                    u[i][2] += u[j++][2];
                u.erase(u.begin() + i + 1, u.begin() + j);
                i++;
            }
            vector<int> a(n, 0);
            for (auto x : u)
                for (int i = x[0]; i <= x[1]; i++)
                    a[i] += x[2];
            return a;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.