【LeetCode】986. Interval List Intersections 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：Python, two pointer
2. 解答2:
メモ・参考・感想

問題

原文

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [start_i, end_i] and secondList[j] = [start_j, end_j]. 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]]

1
2

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

Example 2:

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

1
2

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

Constraints:

0 <= firstList.length, secondList.length <= 1000

firstList.length + secondList.length >= 1

0 <= start_i < end_i <= 10⁹

end_i < start_i+1

0 <= start_j < end_j <= 10⁹

end_j < start_j+1

内容

2つの閉じた区間のリストが与えられます。それぞれのリストは[start, end]として開始～終了までの区間を表します。それぞれの区間は1:1で対応しており、ソートされています。

2つの区間の共通区間を返してください。

閉区間[a,b]は、a<=x<=bである実数xの集合を表します。

2つの閉区間の共通区間は、空であるか、閉区間として表現される実数の集合です。

例えば、[1,3]と[2,4]の共通区間は[2,3]になります。

※正しくない可能性があります。

解答

解答1：Python, two pointer

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

        #2ポインタを使って2つのリストの小さい方を1つずつ増やしつつ、共通部分を戻り値に追加
        intersection_list = []
        i,j = 0, 0
        #i,jは2ポインタ。最後の要素にたどり着くまで繰り返す        
        while i < len(firstList) and j < len(secondList):

            maximum_start = max(firstList[i][0], secondList[j][0])            
            minimum_end = min(firstList[i][1], secondList[j][1])
            #   0-------2
            #       1-------3
            #この場合、maximum_start=1,minimum_end=2になる
            #1~2は共通区間なので、次の操作で解答の1つとして追加される

            #＜共通部分があれば戻り値に追加する＞
            if maximum_start <= minimum_end:
                intersection_list.append([maximum_start, minimum_end])
            
            #＜終わり位置が小さい方のポインタを1つ増やして2つのリストを進める＞
            #firstListの終わり位置がsecondListの終わり位置よりも小さい場合
            if firstList[i][1] < secondList[j][1]:
                #firstListのポインタを増やし、次の要素へ移る
                i += 1
            #firstListの終わり位置がsecondListの終わり位置よりも大きい場合
            else:
                #secondListのポインタを増やし、次の要素へ移る
                j += 1

        #戻り値を返す
        return intersection_list

class Solution:

def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:

#2ポインタを使って2つのリストの小さい方を1つずつ増やしつつ、共通部分を戻り値に追加

intersection_list = []

i,j = 0, 0

#i,jは2ポインタ。最後の要素にたどり着くまで繰り返す

while i < len(firstList) and j < len(secondList):

maximum_start = max(firstList[i][0], secondList[j][0])

minimum_end = min(firstList[i][1], secondList[j][1])

# 0-------2

# 1-------3

#この場合、maximum_start=1,minimum_end=2になる

#1~2は共通区間なので、次の操作で解答の1つとして追加される

#＜共通部分があれば戻り値に追加する＞

if maximum_start <= minimum_end:

intersection_list.append([maximum_start, minimum_end])

#＜終わり位置が小さい方のポインタを1つ増やして2つのリストを進める＞

#firstListの終わり位置がsecondListの終わり位置よりも小さい場合

if firstList[i][1] < secondList[j][1]:

#firstListのポインタを増やし、次の要素へ移る

i += 1

#firstListの終わり位置がsecondListの終わり位置よりも大きい場合

else:

#secondListのポインタを増やし、次の要素へ移る

j += 1

#戻り値を返す

return intersection_list

解答2:

メモ・参考・感想

前：844. Backspace String Compare

次：200. Number of Islands

LeetCode 解答・解説記事一覧