Leetcode 1028 Solution

This article provides solution to leetcode question 1028 (interval-list-intersections).
Categories:
Tags:
Access this page by simply typing in "lcs 1028" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/interval-list-intersections

Solution

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def intervalIntersection(self, A, B):
        """
        :type A: List[Interval]
        :type B: List[Interval]
        :rtype: List[Interval]
        """
        heap = []
        for a in A + B:
            heapq.heappush(heap, (a.start, -1))
            heapq.heappush(heap, (a.end, 1))

        l = sys.maxsize
        cur = 0
        ans = []
        while heap:
            i, v = heapq.heappop(heap)
            cur += v

            if cur == -2:
                l = i
            else:
                if l > i:
                    continue

                ans.append((l, i))
                l = sys.maxsize

        return ans