Python 3 | Sweep Line, Heap | Explanations
Explanation\n- Typical Sweep Line question, use heap for help\n- Mark every start as -1, every end as 1\n- Sort all start & end points\n- Close interval only wh
### Explanation\n- Typical `Sweep Line` question, use `heap` for help\n- Mark every start as `-1`, every end as `1`\n- Sort all start & end points\n- Close interval only when counter `cur` equals to `0`\n- Check out below comments for more detail\n### Implementation\n```\nclass Solution:\n    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:\n        heap, ans, = [], [] \n        for s, e in intervals + [newInterval]: # add start & end to heap (-1 is start, 1 is end)\n            heapq.heappush(heap, (s, -1))\n            heapq.heappush(heap, (e, 1))\n        cur, s = 0, None            \n        while heap:                            \n            i, val = heapq.heappop(heap)       # pop heap\n            if s is None: s = i                # is s is None, assign i to s (interval start)\n            cur += val                         # keep counting until close interval\n            if not cur:                        # when cur == 0, meaning we can close the interval\n                ans.append([s, i])             # append interval to ans\n                s = None                       # reset s to None\n        return ans        \n```
['Greedy', 'Heap (Priority Queue)', 'Python', 'Python3']