Pythonでカット区間と交差しない区間を求めるプログラムの実装方法

ソート済みで互いに重なり合わない区間（インターバル）のリストと、削除対象となる1つの区間「カット」が与えられたとします。この課題では、カット区間と交差している部分をすべて取り除き、残った区間を新しいリストとして返すプログラムを作成します。

例えば、入力が intervals = [[2, 11], [13, 31], [41, 61]]、cut = [8, 46] の場合、出力は [[2, 8], [46, 61]] になります。

解決のためのアルゴリズム

以下の手順で問題を解くことができます。

1. カット区間の始点・終点をそれぞれ cut_start、cut_end に代入します。
2. 結果を格納するための空リスト ans を用意します。
3. intervals 内の各区間 (start, end) に対して次の処理を行います。
   max(cut_start, start) < min(end, cut_end) が成立するとき、その区間はカットと交差しています。この場合、
   ・start < cut_start ならば、区間 [start, cut_start] を ans に追加する
   ・end > cut_end ならば、区間 [cut_end, end] を ans に追加する
   一方、条件が成立しない（交差していない）場合は、元の区間 [start, end] をそのまま ans に追加します。
4. すべての区間を処理し終えたら、ans を返します。

実装例（Pythonコード）

class Solution:
    def solve(self, intervals, cut):
        cut_start, cut_end = cut
        ans = []
        for start, end in intervals:
            if max(cut_start, start) < min(end, cut_end):
                # カットと交差している場合は、はみ出た部分だけを残す
                if start < cut_start:
                    ans.append([start, cut_start])
                if end > cut_end:
                    ans.append([cut_end, end])
            else:
                # 交差していない場合はそのまま追加
                ans.append([start, end])
        return ans

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

入力

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

出力

[[2, 8], [46, 61]]

処理の流れを詳しく解説

サンプル入力における各区間の処理は次のとおりです。

• [2, 11]：max(8, 2) = 8 < min(11, 46) = 11 となり、カットと交差しています。start = 2 が cut_start = 8 より小さいため左側の [2, 8] が残ります。一方、end = 11 は cut_end = 46 より大きくないため、右側は残りません。
• [13, 31]：max(8, 13) = 13 < min(31, 46) = 31 で交差していますが、区間全体がカット範囲に含まれているため、何も残りません。
• [41, 61]：max(8, 41) = 41 < min(61, 46) = 46 で交差しています。end = 61 が cut_end = 46 より大きいため、右側の [46, 61] が残ります。

このように、交差判定には「2つの始点のうち大きい方」が「2つの終点のうち小さい方」より小さいかどうかという条件式を使うのがポイントです。これは2つの区間が重なっているかどうかを判定する際の定番手法なので、覚えておくとさまざまな場面で応用できます。