986. Interval List Intersections (Array, Two Pointers, Line Sweep)

링크 - https://leetcode.com/problems/interval-list-intersections/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 두개의 값중 첫번째 값의 max와 두번째 값의 min을 통해서 두개에 intersection이 있는지 없는지를 알 수 있다. 그리고 항상 end가 낮은 리스트 인덱스를 올려준다.

Code

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        idx1 = idx2 = 0

        ans = []
        while idx1 < len(firstList) and idx2 < len(secondList):
            lo = max(firstList[idx1][0], secondList[idx2][0])
            hi = min(firstList[idx1][1], secondList[idx2][1])

            if lo <= hi:
                ans.append([lo, hi])

            if firstList[idx1][1] < secondList[idx2][1]:
                idx1 += 1
            else:
                idx2 += 1

        return ans

Complexity

Time Complexity: O(M+N)

Space Complexity: O(M+N)