[C++] Sweep line based approach with lazy computation
Intuition:\n\n1. In the given problem, we are given two APIs: add to add a specific interval and count to get the number of integers included in the already add
Intuition:\n\n1. In the given problem, we are given two APIs: `add` to add a specific interval and `count` to get the number of integers included in the already added intervals.\n2. In order to implement `add`, we need to find a way to efficiently mark the added interval.\n\t1. Let\'s assume that we have a number line where we mark all the integers which are part of interval. For instance,\n\t```\n\t0 0 0 0 0 0  => occurrence\n\t1 2 3 4 5 6 => integers\n\t```\n\t2. Let\'s say I add interval [2,4] to it, my number line will look something like this:\n\t```\n\t0 1 1 1 0 0  => occurrence\n\t1 2 3 4 5 6 => integers\n\t```\n\t3. For smaller constraints, It may be done. But for larger constraints, Let\'s say [1,10^9], It is **not feasible**.\n\t4. Hence, Instead of marking each and every integer, We only mark the boundaries of the interval. For instance,\n\t```\n\t0 0 0 0 0 0  => occurrence\n\t1 2 3 4 5 6 => integers\n\t```\n\t5. Now on adding [2,4] to it, We will add 1 to 2 (to mark the starting of interval) and -1 to 5 (to mark the end of the interval).\n\t```\n\t0 1 0 0 -1 0  => occurrence\n\t1 2 3 4 5 6 => integers\n\t```\n\t6. Now, the **cumulative sum** at any given integer can tell me whether it is included in some interval. **If its non zero, it means that it is included.**\n\t7. But there is another problem. This approach requires creating a big array of integers (probably of size 10^9) which will end up giving **memory limit exceeded** issues.\n\t8. Instead, What we can do is we can store the boundaries in a ordered map. For instance, \n    ```\n\t[] => ordered map\n\t```\n\t9. On adding [2, 4], It will look something like this:\n\t```\n\t[[2, 1], [5, -1]] => ordered map\n\t```\n3. For `count`,\n    1. We can traverse the ordered map created by adding the intervals and determine the number of integers by considering the **cumulative sum**.\n    2. One important thing to note here is that we can merge our intervals at this phase only. This will help us in optimising our future `add` and `count` calls since merged intervals will always be smaller.\n\t\t1. If cumulative sum is 0 before processing a event (or boundary), that means that it is a **start** of the merged interval.\n\t\t2. If cumulative sum is 0 after processing a event (or boundary), that means that it is a **end** of the merged interval.\n\nHere is the C++ Code:\n\n```\nclass CountIntervals {\n    map<int, int> events; /* to store start and end events */\n    int lastCnt; /* to store last count. This avoids recomputation in case of subsequent count() calls */\n    \npublic:\n    CountIntervals(): lastCnt(-1) {\n        \n    }\n    \n    void add(int left, int right) {\n\t    /*\n\t\t\tAdding +1 for marking start, -1 for marking end.\n\t\t\tright + 1 is being done since both start and end are inclusive.\n\t\t\tSet lastCnt to -1 since recomputation has to be done.\n\t\t*/\n        events[left]++, events[right + 1]--, lastCnt = -1;\n    }\n    \n    int count() {\n\t    /* If recomputation has to be done */\n        if (lastCnt == -1) {\n            lastCnt = 0;\n\t\t\t/* curInt stores number of active intervals,\n\t\t\tllim stores starting position of currently active merged interval */\n            int curInt = 0, llim = 0;\n            \n\t\t\t/* map to store merged events */\n            map<int, int> newEvents;\n            \n            for (const auto& p: events) {\n\t\t\t    /* if no ongoing merged interval, then this is our start of our merged interval */\n                if (curInt == 0) {\n                    llim = p.first, newEvents[llim]++;\n                }\n                \n                curInt += p.second;\n\t\t\t\t\n\t\t\t\t/* If after adding p.second, curInt is zero, it means that we have found the end of merged interval */\n                if (curInt == 0) {\n                    lastCnt += (p.first - llim), newEvents[p.first]--;\n                }\n            }\n            \n\t\t\t/* assigning merged intervals to originally stored intervals. */\n            events = newEvents;\n        }\n        \n        return lastCnt;\n    }\n};\n```
[]