Pythonで区間リストから重複しない期間の合計を求めるプログラム

各要素が区間 [start, end]（両端を含む）を表すリストのリストがあるとします。このとき、これらの区間が実際にカバーしている重複しない期間の合計を求めたいと思います。

例えば、入力が intervals = [[2, 11], [13, 31], [41, 61]] の場合を考えてみましょう。各区間がカバーする長さはそれぞれ以下のようになります。

• (11 − 2 + 1) = 10
• (31 − 13 + 1) = 19
• (61 − 41 + 1) = 21

これらの区間は互いに重なり合っていないため、合計は 10 + 19 + 21 = 50 となります。

解決のためのアプローチ

この問題は、区間をソートして隣接する区間を順次マージしていくことで効率的に解けます。手順は以下の通りです。

1. 区間リストが空の場合は 0 を返します。
2. 区間リストをソートします。
3. 最初の区間を [start, end] として取得します。
4. 答えを格納する変数 ans を 0 で初期化します。
5. 各区間 (s, e) について以下を繰り返します。
   • s > end の場合（現在の区間と重ならない場合）：
     ans += end - start + 1 でこれまでの区間の長さを加算し、start = s、end = e として新しい区間を開始します。
   • そうでない場合（重なる場合）：
     end = max(end, e) として現在の区間の終点を拡張します。
6. ループ終了後、最後の区間の長さ end - start + 1 を ans に加算します。
7. ans を返します。

実装例

以下のコードで具体的な実装を確認してみましょう。

class Solution:
    def solve(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        start, end = intervals[0]
        ans = 0
        for s, e in intervals:
            if s > end:
                ans += end - start + 1
                start = s
                end = e
            else:
                end = max(end, e)
        ans += end - start + 1
        return ans

ob = Solution()
intervals = [[2, 11],[13, 31],[41, 61]]
print(ob.solve(intervals))

入力

[[2, 11],[13, 31],[41, 61]]

出力

50

アルゴリズムのポイント

このアプローチの計算量は、ソートに O(n log n)、マージ処理に O(n) かかるため、全体として O(n log n) です。区間を先にソートしておくことで、隣接する区間との比較だけで済み、すべての区間同士の組み合わせを調べる必要がなくなります。また、重複する区間（例：[1, 5] と [3, 8]）が含まれていても、max(end, e) によって正しく統合されるため、二重カウントを防げるのが特徴です。