🔥Python3🔥 merge interval solution (Explained) space complexity O(n) / O(1)
Intuition\n\nThis problem is almost the same as 56. Merge Intervals if we first insert newInterval into intervals such that intervals is still sorted by the sta
**Intuition**\n\nThis problem is almost the same as [56. Merge Intervals](https://leetcode.com/problems/merge-intervals/) if we first insert ```newInterval``` into ```intervals``` such that ```intervals``` is still sorted by the start time, and then merge overlapped intervals.\n\n - use binary search to find the index where ```newInterval``` should be instered into ```intervals```. O(logN)\n - Insert the ```newInterval```. O(N)\n - merge overlapped intervals if there are any.\n    - We can interately build a stack, and merge a new interval with the last interval in the stack if they overlap.\n    - To check if a new interval is overlap with the last interval in stack, we simply check if the last end is greater than or equal to the new start. If it is, we merge the two intervals by using the last start as the start, and the max(lastEnd, newEnd) as the end.\n    - If there is no overlap between the new interval and the last interval in stack, we simply add the new interval to the stack.\n\n**Solution 1** using stack\n\n```python\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        insertI = bisect_left(intervals, newInterval)\n        intervals.insert(insertI, newInterval)\n        stack = []\n        for s,e in intervals:\n            if stack and stack[-1][1] >= s:\n                lastS,lastE = stack.pop()\n                stack.append([lastS, max(lastE,e)])\n            else:\n                stack.append([s,e])\n        return stack\n```\n\nWe don\'t really need to use a stack, but using the list slicing in Python to merge the overlapped intervals.\n\n**Solution 2** inplace merge\n\n```python\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        insertI = bisect_left(intervals, newInterval)\n        intervals.insert(insertI, newInterval)\n        i = 0\n        while i<len(intervals):\n            s,e = intervals[i]\n            if i>0 and intervals[i-1][1] >= s:\n                lastS,lastE = intervals[i-1]\n                intervals[i-1:i+1] = [[lastS, max(lastE,e)]]\n            else:\n                i += 1\n        return intervals\n```\n\n**Upvote** if you like this post.\n\n**Connect with me on [LinkedIn](https://www.linkedin.com/in/meida-chen-938a265b/)** if you\'d like to discuss other related topics\n\n\uD83C\uDF1F If you are interested in **Machine Learning** || **Deep Learning** || **Computer Vision** || **Computer Graphics** related projects and topics, check out my **[YouTube Channel](https://www.youtube.com/@meidachen8489)**! Subscribe for regular updates and be part of our growing community.\n
[]