【LeetCode】 56. Merge Intervals 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

詳細

問題

原文

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

1
2
3

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.

1
2
3

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10⁴

intervals[i].length == 2

0 <= start_i <= end_i <= 10⁴

内容(和訳)

i番目の要素が区間の開始と終了を示す配列intervalsが与えられます。

各区間の重なりがある場合は結合し、重なりのない区間のリストを返してください。

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

解答

解答1：Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        #各要素の1つ目の値をキーにソート
        intervals.sort(key = lambda x: x[0])
        #余談。↓以下のようにすると2つ目の要素をキーにしてソートできる
        #intervals.sort(key = lambda x: x[1])
        merged_list = []

        #intervalsを走査
        for element in intervals:
            #merged_listに要素がない。もしくは、前区間の終了が、現区間の開始未満の場合
            if not merged_list or merged_list[-1][-1] < element[0]:
                #merged_listに追加する
                merged_list.append(element)
            #上記以外の場合
            else:
                #前区間の終了を以下の大きい方で上書き
                #現区間の終端か、前区間の終端
                #開始で昇順ソートしているので、開始区間でminを取る必要はない
                merged_list[-1][-1] = max(element[1], merged_list[-1][-1])
        
        #merged_listを返す。
        return merged_list

class Solution:

def merge(self, intervals: List[List[int]]) -> List[List[int]]:

#各要素の1つ目の値をキーにソート

intervals.sort(key = lambda x: x[0])

#余談。↓以下のようにすると2つ目の要素をキーにしてソートできる

#intervals.sort(key = lambda x: x[1])

merged_list = []

#intervalsを走査

for element in intervals:

#merged_listに要素がない。もしくは、前区間の終了が、現区間の開始未満の場合

if not merged_list or merged_list[-1][-1] < element[0]:

#merged_listに追加する

merged_list.append(element)

#上記以外の場合

else:

#前区間の終了を以下の大きい方で上書き

#現区間の終端か、前区間の終端

#開始で昇順ソートしているので、開始区間でminを取る必要はない

merged_list[-1][-1] = max(element[1], merged_list[-1][-1])

#merged_listを返す。

return merged_list

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：274. H-Index

次：

LeetCode 解答・解説記事一覧