[Python] 2 solutions: merge intervals + greedy, explained
Solution 1\nLet as keep all possible numbers we can get as list of intervals, for example 0, 1, 2, 4, 5, 12 is [[0, 2], [4, 5], [12, 12]]. Then  when we add new
#### Solution 1\nLet as keep all possible numbers we can get as list of intervals, for example `0, 1, 2, 4, 5, 12` is `[[0, 2], [4, 5], [12, 12]]`. Then  when we add new number we can merge our intervals, using idea of Problem **0056**. What numbers we need to add next? We need to add number `3` in our example, the smallest possible number, which are not in our array. \n\n#### Complexity\nComplexity is `O(m * log n)`, where `m <= 10000` is the biggest value of `num`. The idea is that in the beginning we can have not more than `m//2` intervals and then on each iteration number of intervals can not increase or increase not too fast (I do not have strict proof at the moment). Also number of iterations can not too big, because it is enough `log n` patches always.\n\n#### Code\n```python\nclass Solution:\n    def merge(self, intervals):\n        intervals.sort(key=lambda x: x[0])\n        merged = []\n        \n        for interval in intervals:\n            if not merged or merged[-1][1] < interval[0] - 1:\n                merged.append(interval)\n            else:\n                merged[-1][1] = max(merged[-1][1], interval[1])\n\n        return merged\n\n\n    def minPatches(self, nums, n):\n        ints, patches = [[0,0]], 0\n        for num in nums:\n            ints = self.merge(ints + [[i+num, j+num] for i,j in ints])\n\n        while ints[0][1] < n:\n            ints = self.merge(ints + [[i+ints[0][1]+1, j+ints[0][1]+1] for i,j in ints])\n            patches += 1\n\n        return patches\n```\n\n#### Solution 2\nWe can improve this solution, if we upgrade the idea of smallest number which we do not have yet. \n\n**Example**: `nums = [1, 2, 4, 13, 43]`. We go form the smallest number add them one by one and always keep the possible range of numbers we can get in the form `[0, k]`, that is, it is not union of intervals, but only one interval. Let us go through this example. \n\n1. We did not choose any numbers yet, so we have interval `[0, 0]`.\n2. Are we missing something if we take next number `1`? No, let us take it, now we have interval `[0, 1]`.\n3. Are we missing something if we take next number `2`? No, let us take it, now we have interval `[0, 3]`.\n4. Are we missing something if we take next number `4`? No, let us take it, now we have interval `[0, 7]`.\n5. Are we missing something if we take next number `13`? Yes, we missing! What we need to take next patch equal to `8`. So now, our interval is `[0, 15]`.\n6. Our next missing number `16` is more, than next number in array: `13`. So if fact, we can create `[0, 28]`.\n7. Our next missing number is `29`, it is less than `43`, so we add `29` as patch. and we have interval `[0, 57]`.\n\n#### Complexity\n\nComplexity of this solution is `O(n)`.\n\n#### Code\n```python\nclass Solution:\n    def minPatches(self, nums, n):\n        reach, ans, idx = 0, 0, 0\n        \n        while reach < n:\n            if idx < len(nums) and nums[idx] <= reach + 1:\n                reach += nums[idx]\n                idx += 1\n            else:\n                ans += 1\n                reach = 2*reach + 1       \n                \n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Greedy']