[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で追跡し,2つのポインタで解く.O(n+m)
大きな枠組みの下でアイデアを提出し、実現するのは難しくないが、隅のケースを処理するのは難しい.特に始点が同じ場合はほぼ全ての時間を費やしている.受け入れ率=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]]
その二つの状況だけを補足的に考慮し、条件を増やした.
実際、反例を与えない他のプラットフォームでは、問題を解くのは難しいはずです.
今度は間違っていても反例はできない.時間が迫っていても、自分でテストボックスを作る練習をしなければなりません.

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

ずっと簡潔だ.解答では,コードそのものよりもアイデアの構想に多くの資金を投入した.必ずリンクを見てください.リンクからアイデアを考える過程が役立ちます.
まず,オーバーラップするすべての状況の数を整理した.特にA、Bブロックのみ使用しています.
CRISS-クロスロックが分かれば良いです.
ポインタを移動する基準もstart valueではなくend valueです.疲れ果てて動くという概念がある.