[Leetcode] 986. Interval List Intersections

21.11.24 solved in 60 min.

Problem

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution

class Solution(object):
    def intervalIntersection(self, firstList, secondList):
        """
        :type firstList: List[List[int]]
        :type secondList: List[List[int]]
        :rtype: List[List[int]]
        """
        l1=len(firstList)
        l2=len(secondList)
        
        
        #corner case
        if l1==0 or l2==0:
            return None
        
        i=0
        j=0
        answer=[]
        
        stk1=[]
        stk2=[]
        
        while i<l1 and j<l2:
            if firstList[i][0]<secondList[j][0]:
                if j==0:
                    i+=1
                    continue
                
                if secondList[j-1][1]>=firstList[i][0] and secondList[j-1][0]!=firstList[i][0]:
                    answer.append([firstList[i][0],min(secondList[j-1][1],firstList[i][1])])
                
                i+=1
            elif firstList[i][0]>secondList[j][0]:
                if i==0:
                    j+=1
                    continue
                
                if firstList[i-1][1]>=secondList[j][0] and firstList[i-1][0]!=secondList[j][0]:
                    answer.append([secondList[j][0],min(firstList[i-1][1],secondList[j][1])])
                
                j+=1
            else:
                answer.append([secondList[j][0],min(firstList[i][1],secondList[j][1])])
                if firstList[i][1]>secondList[j][1]:
                    j+=1
                elif firstList[i][1]<secondList[j][1]:
                    i+=1
                else:
                    i+=1
                    j+=1
        
        while i<l1 and firstList[i][0]<=secondList[-1][1]:
            if firstList[i][0]!=secondList[-1][0]:
                answer.append([firstList[i][0],min(firstList[i][1],secondList[-1][1])])
            i+=1
        
        while j<l2 and secondList[j][0]<=firstList[-1][1]:
            if secondList[j][0]!=firstList[-1][0]:
                answer.append([secondList[j][0],min(secondList[j][1],firstList[-1][1])])
            j+=1           
        
                
        
        return answer

i,j로 tracing하여 two pointer로 풀었다. O(n+m)
큰 틀에서 아이디어 내고 구현하는 것은 어렵지 않았지만 corner cases 처리하는 것이 많이 까다로웠다. 특히 시작점이 같은 경우를 핸들링하는데 시간을 거의다 소비했다. acceptance rate = 25%로 풀어서 아쉬웠다.

다음과 같은 상황에서 오류가 났고 수정 하였다.

Input:
[[5,10]]
[[5,6]]
Output:
[[5,6],[5,6]]
Expected:
[[5,6]]

Input:
[[8,15]]
[[2,6],[8,10],[12,20]]
Output:
[[8,10],[8,10],[12,15]]
Expected:
[[8,10],[12,15]]

딱 저 두가지 경우에 대해서만 추가로 생각해서 condition을 덧붙였다.
사실 반례를 주지 않는 다른 플랫폼에서는 푸는게 힘들었을 것 같다.
다음부터 틀려도 반례는 최대한 보면 안 되겠다. 시간이 급해도 스스로 테스트 케이스 만드는 연습도 해야한다.

Best Solution

https://leetcode.com/problems/interval-list-intersections/discuss/647482/Python-Two-Pointer-Approach-%2B-Thinking-Process-Diagrams

 class Solution:
     def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
         i = 0
         j = 0
         
         result = []
         while i < len(A) and j < len(B):
             a_start, a_end = A[i]
             b_start, b_end = B[j]
             if a_start <= b_end and b_start <= a_end:                       # Criss-cross lock
                 result.append([max(a_start, b_start), min(a_end, b_end)])   # Squeezing
                 
             if a_end <= b_end:         # Exhausted this range in A
                 i += 1               # Point to next range in A
             else:                      # Exhausted this range in B
                 j += 1               # Point to next range in B
         return result

훨씬 간결햐다. 풀이에서도 코드 자체보다 아이디어 구상하는데 훨씬 투자를 많이 했다. 링크 꼭 봐야한다. 링크에서 아이디어를 떠올리는 과정이 도움이 많이 된다.
우선 overlap이 생기는 모든 경우의 수를 정리했다. 특히 A, B chunk 하나씩만 사용해서 나타내었다.
criss-cross locking 알아두면 좋을 듯.

pointer를 움직이는 기준도 start value가 아닌 end value이다. exhausted하면 이동한다는 컨셉을 가지고 있다.