Swift Merge Intervals
Intuition\nWe would keep a sorted non-overlapping intervals array during add. At counting stage we just count all the elements in interval\n\n# Approach\n1. Lis
# Intuition\nWe would keep a sorted non-overlapping intervals array during add. At counting stage we just count all the elements in interval\n\n# Approach\n1. List out all possibilities of interval merging pattern, and come up with interval merging logic\n2. Update count during adding/merging intervals to make count() O(1)\n3. Use binary search to find insertion index\n\n# Complexity\n- Time complexity:\nAdd O(n)\nCount O(1)\n\n- Space complexity:\nO(n)\n\n# Code\n```swift []\n\nclass CountIntervals {\n    var intervals : [[Int]]\n    var c : Int\n\n    init() {\n        intervals = [[Int]]()\n        c = 0\n    }\n\n    func find(_ target: Int) -> Int {\n        var l = 0, r = intervals.count\n        while l < r {\n            let m = (l + r) / 2\n            if intervals[m][1] < target {\n                l = m + 1\n            } else {\n                r = m\n            }\n        }\n        return l\n    }\n    \n    func add(_ left: Int, _ right: Int) {\n        // find index where intervals[i][1] >= left\n        var i = find(left)\n\n        if i == intervals.count {\n            // case 1: insert at the end\n            intervals.append([left, right])\n            c += right - left + 1\n        } else if intervals[i][0] > right {\n            // case 2: insert without merging\n            intervals.insert([left, right], at: i)\n            c += right - left + 1\n        } else {\n            // case 3: merge right\n            \n            // left is determined\n            var newLeft = min(left, intervals[i][0])\n            var newRight = right\n\n            // find right\n            while i < intervals.count, intervals[i][0] <= right {\n                newRight = max(right, intervals[i][1])\n                c -= intervals[i][1] - intervals[i][0] + 1\n                intervals.remove(at: i)\n            }\n            // at this point, intervals[i][0] > right, so we should insert at position i\n            intervals.insert([newLeft, newRight], at: i)\n            c += newRight - newLeft + 1\n        }\n    }\n    \n    func count() -> Int {\n        return c\n    }\n}\n\n/**\n * Your CountIntervals object will be instantiated and called as such:\n * let obj = CountIntervals()\n * obj.add(left, right)\n * let ret_2: Int = obj.count()\n */\n```
['Swift']