[Python] Merge intervals O(n) solution, explained
If we look carefully at this problem we can see that all we need to do is to merge some intervals with equal length and return total length of merged intervals.
If we look carefully at this problem we can see that all we need to do is to merge some intervals with equal length and return total length of merged intervals. Note also that intervals are already sorted by its beginings (and ends as well, because they have equal length), so usual sorting step can be skipped.\n \n All we need to do is to traverse our `timeSeries` and check if difference between current point and previous is more than `duration`. If it is more, we add `duration` to total sum, if it is less, we add difference between current and previous elements. Also we need to deal with border case of empty array and if array is not empty, add `duration` in the end. \n \n **Complexity**: time complexity is `O(n)`, space complexity is `O(1)`.\n\n```\nclass Solution:\n    def findPoisonedDuration(self, timeSeries, duration):\n        n, out = len(timeSeries), 0\n        if n == 0: return 0\n        for i in range(n-1):\n            out += min(timeSeries[i+1] - timeSeries[i], duration)\n        return out + duration\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]