56.連結区間(Python)

939 ワード

もっと素晴らしい内容は、「力ボタン中等問題」に注目してください.
タイトル
難易度:★☆☆タイプ:配列方法:並べ替え
区間の集合を指定します.重複するすべての区間をマージしてください.
例1入力:[[1,3],[2,6],[8,10],[15,18]]出力:[[1,6],[8,10],[15,18]]解釈:区間[1,3]と[2,6]が重なる、それらを[1,6]にまとめる.
例2入力:[[1,4],[4,5]]出力:[[1,5]]解釈:区間[1,4]および[4,5]はオーバーラップ区間とみなすことができる.
に答える
まず、すべての区間を開始位置に並べ替えて、結果リストを準備し、一つ一つ遍歴して、新しく結果リストに追加された区間が結果リストの最後の区間と一致しているかどうかを確認し、一致すれば更新し、そうでなければ直接結果リストに追加します.
class Solution:
    def merge(self, intervals):
        """
        :param intervals: List[List[int]]
        :return: List[List[int]]
        """

        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][-1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][-1] = max(merged[-1][-1], interval[-1])
        return merged

質問やアドバイスがあれば、コメントエリアへようこそ~