Leetcode 986 Interval List Intersections

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].

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]]

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

• Soruda bize iki interval listesi veriliyor.İntervalleri doğru parçaları olarak düşünebiliriz. Bu iki interval listesindeki kesişimlerden yeni bir interval listesi oluşturmamız isteniyor.
• Soru da yapacağımız listedeki intervalleri karşılaştırarak başlangıç değerlerinin maksimumunu bitiş değerlerinin ise minimumu alarak kesişim intervali oluşturmak.[0,2] ve [1,5] için [1,2] oluşur.
• Burada dikkat etmemiz gereken iki listeyi karşılaştırırken sadece aynı indeksteki intervalleri karşılaştırmamak bunu yaparsak aradaki bazı kesişimleri kaçırabiliriz.
• Sıfırıncı indeksteki intervalleri karşılaştırmayı bitirince karşılaştırdığımız intervallerin hangisinin bitiş(end) değeri düşükse o listedeki bir sonraki intervale geçeriz.Bu sayede çapraz kontroller yaparak aradaki kesişimleri de bulabiliriz.

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        a = 0
        b = 0
        intervals = []
        
        while a < len(A) and b < len(B):
            intervalStart,intervalEnd = max(A[a][0],B[b][0]), min(A[a][1],B[b][1])
            
            if intervalStart <= intervalEnd:
                intervals.append([intervalStart,intervalEnd])
            
            if A[a][1] < B[b][1]:
                a += 1
            else:
                b +=1
        return intervals