C++ Merge Interval + Line Sweep + Dynamic Segment Tree Solution
Merge Interval Solution:\n\nRuntime: 734 ms, faster than 100.00% of C++ online submissions for Count Integers in Intervals.\nMemory Usage: 186.2 MB, less than 8
**Merge Interval Solution:**\n\nRuntime: 734 ms, faster than 100.00% of C++ online submissions for Count Integers in Intervals.\nMemory Usage: 186.2 MB, less than 83.33% of C++ online submissions for Count Integers in Intervals.\n\n\n```\nMerge intervals in the range start to end in Map and update total count.\nStore updated start and end pair in BST Map.\n```\n\n\n```\nclass CountIntervals {\npublic:\n    \n    // store intervals in start and end pair\n    map<int,int>track;\n    int total;\n    \n    CountIntervals() \n    {\n        total = 0;\n    }\n\n    void add(int left, int right) {\n\n        // get upper bound of the left\n        auto iter = track.upper_bound(left);\n        \n        int minRange = left;\n        int maxRange = right;\n        \n        // if not first element then check previous element\n        if(iter!=track.begin())\n        {\n            auto piter = prev(iter);\n            \n            // if previous interval overlaps with current interval deduct count and merge range\n            if(piter->second >= left)\n            {\n                minRange = min(minRange,piter->first);\n                maxRange = max(maxRange,piter->second);\n                total -= (piter->second-piter->first+1);\n                \n                // delete overlapped interval\n                track.erase(piter);\n            }\n        }\n        \n        // loop until current interval overlaps with Map intervals\n        while(iter!=track.end() && iter->first<=right)\n        {\n            maxRange = max(maxRange,iter->second);\n            total -= (iter->second-iter->first+1);\n            \n            // delete overlapped interval\n            track.erase(iter++);\n        }\n        \n        // update total count with merged range\n        total += maxRange - minRange + 1;\n        \n        // store updated range in Map\n        track[minRange] = maxRange;\n    }\n\n    int count() {\n\n        return total;\n    }\n};\n```\n\n\n**Line Sweep Solution:**\n\nRuntime: 819 ms, faster than 83.33% of C++ online submissions for Count Integers in Intervals.\nMemory Usage: 205.2 MB, less than 83.33% of C++ online submissions for Count Integers in Intervals.\n\n```\nMerge Intervals using Line Sweep in count API call if BST is modified.\nUpdate previous BST with modified BST.\nMark start as +1 and end+1 as -1 in BST in add API call.\n```\n\n```\nclass CountIntervals {\npublic:\n\n    // BST to track the start and end of intervals\n    map<int,int>track;\n    int total;\n    bool modified;\n    \n    CountIntervals() {\n        total = 0;\n        modified = false;\n    }\n\n    void add(int left, int right) {\n\n        // mark start as +1 and end+1 as -1 \n        track[left]++;\n        track[right+1]--;\n        \n        // mark BST as modified\n        modified = true;\n    }\n\n    int count() {\n\n        // perform line sweep if BST modified\n        if(modified)\n        {\n            total = 0;\n            int curr = 0;\n            int start;\n            \n            // store merged start and end in new BST\n            map<int,int>mtrack;\n            \n            for(const auto &iter : track)\n            {\n                // start of interval\n                if(curr==0)start = iter.first;\n                \n                curr+= iter.second;                \n                \n                // end of interval\n                if(curr==0)\n                {\n                    // update merged start and end in new BST\n                    mtrack[start]++;\n                    mtrack[iter.first]--;\n                    \n                    // interval length\n                    total+= iter.first - start;\n                }                \n            }\n            \n            // store merged intervals of new BST\n            track = mtrack;\n        }\n        \n        modified = false;\n        return total;\n    }\n};\n\n```\n\n\n**Dynamic Segment Tree Solution:**\n\nRuntime: 1262 ms, faster than 16.67% of C++ online submissions for Count Integers in Intervals.\nMemory Usage: 609.3 MB, less than 33.33% of C++ online submissions for Count Integers in Intervals.\n\n\n```\n1. Update ranges in dynamic segment tree and update ranges covered for node from child nodes\n2. Early return for non overlap case\n3. Early return for node covered total range\n4. Lazy propagate node cover to child nodes\n5. Return root node range cover count when count API is called\n```\n\n```\nclass SegmentTree\n{\npublic:\n    struct Node\n    {\n        Node* left;\n        Node* right;\n        int val;\n        bool lazy;\n    };\n\n    Node* root;\n    int LIMIT = 1000000001;\n\n    Node* getNode()\n    {\n        Node* node = new Node();\n        node->left = NULL;\n        node->right = NULL;\n        node->val = 0;\n        node->lazy = false;\n\n        return node;\n    }\n\n    SegmentTree()\n    {\n        root = getNode();\n    }\n\n    int getTotal()\n    {\n        return root->val;\n    }\n    \n    void update(Node* node, int lower, int upper, int& left, int& right)\n    {\n        // return for non-overlap case\n        if (lower > right || upper < left) return;\n        \n        if (lower != upper)\n        {\n            if (!node->left)node->left = getNode();\n            if (!node->right)node->right = getNode();\n        }\n\n        // propagate lazy value to child nodes and update current value with lazy value\n        if (node->lazy)\n        {\n            node->val = upper-lower+1;  // total range\n            if (lower != upper)\n            {\n                node->left->lazy = node->lazy;\n                node->right->lazy = node->lazy;\n            }\n            node->lazy = false;\n        }\n\n        // all ranges are covered then return \n        if(node->val == upper-lower+1) return;\n        \n        // update value with total range in case of full-overlap and propagate lazy value to child nodes \n        if (lower >= left && upper <= right)\n        {\n            node->val = upper - lower + 1;  // total range\n            if (lower != upper)\n            {\n                node->left->lazy = true;\n                node->right->lazy = true;\n            }\n\n            node->lazy = false;\n            return;\n        }\n\n        int mid = lower + (upper - lower) / 2;\n\n        update(node->left, lower, mid, left, right);\n        update(node->right, mid + 1, upper, left, right);\n\n        // update node range from child node ranges\n        node->val = node->left->val + node->right->val;\n    }\n\n    void updateVal(int left, int right)\n    {\n        update(root, 1, LIMIT, left, right);\n    }\n};\n\nclass CountIntervals {\npublic:\n    \n    SegmentTree tree;\n    CountIntervals() {}\n\n    void add(int left, int right) {\n\n        // update range from left to right in Segment tree\n        tree.updateVal(left,right);\n    }\n\n    int count() {\n\n        // return total ranges covered by root node\n        return tree.getTotal();\n    }\n};\n```
['Tree', 'C', 'Counting']