Pythonで点を含まない最も広い2点間の垂直領域を求めるプログラム

問題の概要

n個の点が(x, y)という形式で与えられているとします。「垂直領域」とは、y軸方向に無限に延びる領域のことです。この問題では、他のどの点も内部に含まず、かつ最も幅が広い2点間の垂直領域を見つける必要があります。

入力例

例えば、入力が pts = [[10,9],[11,11],[9,6],[11,9]] の場合、出力は 1 となります。

下図の赤と青で示された領域が最適解であり、これらの領域内には点が一切存在しません。

解法のアプローチ

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

1. リスト pts をソートします。
2. i を 1 から pts のサイズまで繰り返し処理します。
3. (pts[i][0] - pts[i-1][0]) の最大値を返します。

このアプローチのポイントは、x座標でソートすることで、隣接する2点間のx座標の差だけを調べればよくなる点です。垂直領域はy軸方向に無限に伸びるため、その幅はx座標の差のみで決まります。また、ソート後の隣接する点の間には他の点が存在しないため、必ず「空の垂直領域」になることが保証されます。

実装例

以下のPythonコードで実装方法を確認できます。

def solve(pts):
   pts.sort()
   return max(pts[i][0] - pts[i - 1][0] for i in range(1, len(pts)))
print(solve([[10,9],[11,11],[9,6],[11,9]]))

入力

[[10,9],[11,11],[9,6],[11,9]]

出力

1

計算量について

この解法の時間計算量は O(n log n) です。これは主にソートにかかるコストによるものです。一方、空間計算量は O(1) となり、追加のメモリをほとんど必要としない効率的なアルゴリズムです。