Pythonで長方形を幅の非増加順に並べ替えられるか判定する方法

各長方形が縦と横の寸法で表されたリストがあるとします。任意の長方形は90度回転できるため、回転すると縦と横の値が入れ替わります。ここで、すべての長方形の幅が非増加順（前の要素以下になっていく順序）となるように並べ替えられるかどうかを判定する問題を考えます。

例えば、入力が rects = [[4, 5], [5, 7], [4, 6]] の場合、出力は True となります。初期状態では幅が [5, 7, 6] ですが、後ろの2つの長方形を回転させると幅は [5, 5, 4] となり、非増加順に並んでいることが分かります。

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率的に解くことができます。左から順に長方形を走査し、それぞれの長方形について、直前の長方形の幅以下になるような向きを選択していきます。具体的な手順は以下の通りです。

• 変数 m を十分大きな値（99999など）で初期化します。
• i 番目の長方形について、縦と横の大きい方（max）が m 以下であれば、m をその大きい方の値で更新します。
• そうでない場合、小さい方（min）が m 以下であれば、その長方形を回転したとみなし、m を小さい方の値で更新します。
• どちらの条件も満たさない場合は、非増加順に並べることができないため False を返します。
• すべての長方形を処理できたら True を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

def solve(rect):
    m = 99999
    for i in range(len(rect)):
        if max(rect[i][0], rect[i][1]) <= m:
            m = max(rect[i][0], rect[i][1])
        elif min(rect[i][0], rect[i][1]) <= m:
            m = min(rect[i][0], rect[i][1])
        else:
            return False
    return True

rects = [[4, 5], [5, 7], [4, 6]]
print(solve(rects))

入力

[[4, 5], [5, 7], [4, 6]]

出力

True