区間被覆問題
区間被覆問題（Interval Covering Problem）を効率的に解くためのPythonライブラリ（モジュール）
この問題は、「指定されたターゲット区間 $[S, E]$ を、与えられた複数の部分区間から最小限の個数を選んで完全にカバーする」という最適化問題です。効率的な貪欲法（Greedy Algorithm）を用いて、計算量 $O(N \log N)$ で最適解を求めます。
def solve_interval_cover(target_start, target_end, intervals):
"""
ターゲット区間 [target_start, target_end] を最小の区間数で被覆する関数。
Parameters:
target_start (int/float): カバーしたい範囲の開始点
target_end (int/float): カバーしたい範囲の終了点
intervals (list of list/tuple): [開始, 終了] または [開始, 終了, ラベル] のリスト
例: [[0, 3, "A"], [1, 5, "B"], ...]
Returns:
list: 選択された区間のリスト（各要素は入力と同じ形式）
"""
# データを内部で扱いやすいように整形 (start, end, label)
# ラベルがない場合は None を設定
formatted_intervals = []
for item in intervals:
start, end = item[0], item[1]
label = item[2] if len(item) > 2 else None
formatted_intervals.append((start, end, label))
# 開始点の昇順、同じ開始点なら終了点の降順でソート
sorted_intervals = sorted(formatted_intervals, key=lambda x: (x[0], -x[1]))
selected = []
current_end = target_start
n = len(sorted_intervals)
i = 0
while current_end < target_end:
best_interval = None
max_end = current_end
# 現在のカバー範囲の開始時点（current_end）以下で始まり、
# 最も遠くまで届く（endが最大の）区間を探す
while i < n and sorted_intervals[i][0] <= current_end:
if sorted_intervals[i][1] > max_end:
max_end = sorted_intervals[i][1]
best_interval = sorted_intervals[i]
i += 1
# 新たに範囲を広げられない場合はカバー不可能
if best_interval is None or max_end <= current_end:
return []
selected.append(best_interval)
current_end = max_end
# 出力形式を入力のリスト構造（3要素なら3要素、2要素なら2要素）に合わせる
output = []
for item in selected:
start, end, label = item
if label is not None:
output.append([start, end, label])
else:
output.append([start, end])
return output# 1. ターゲット範囲の設定
target_start = 0
target_end = 10
# 2. [開始, 終了, ラベル(任意)] のリスト形式で区間を定義
available_intervals = [
[0, 3, "A"],
[1, 5, "B"],
[3, 8, "C"],
[4, 9, "D"],
[8, 10, "E"],
[2, 4, "F"]
]
# ラベル無しのシンプル形式 [[0, 3], [1, 5], ...] でも動作します
# 3. 求解
result = solve_interval_cover(target_start, target_end, available_intervals)
# 4. 結果の出力
if result:
print(f"最小被覆に必要な区間数: {len(result)}")
print("選択された区間:")
for iv in result:
print(f" - {iv}")
else:
print("指定された範囲を完全にカバーすることは不可能です。")