C++で長方形を入れ子にした後に残る長方形の最小数を求める方法

問題概要

N個の異なる長方形について、それぞれの幅と高さが与えられているとします。このとき、ある長方形を別の長方形の中へ入れ子状に挿入していった後、最終的に残る長方形の数の最小値を求めるのが本記事のテーマです。

ここで、長方形R1とR2の幅をそれぞれW1・W2、高さをH1・H2とすると、W1 < W2 かつ H1 < H2 が成り立つ場合に限り、長方形R1は長方形R2の中に完全に収まります。この性質により、最も小さな長方形は2番目に小さな長方形の中へ、さらにそれは次の長方形の中へ、というように順々に入れ子にしていくことが可能です。

入力例と出力

例えば、入力が {{30, 45}, {15,15}, {45,30}, {60,75}} の場合、出力は 2 となります。入れ子の組み合わせの一例としては、2番目の長方形（15×15）を1番目の長方形（30×45）に挿入し、さらにその長方形を4番目の長方形（60×75）に挿入する方法があります。この結果、残るのは3番目と4番目の長方形の2つです。

解決のための手順

この問題は、ソートと二分探索を組み合わせることで効率的に解くことができます。具体的な手順は以下の通りです。

• n を boxes のサイズとします
• boxes をサイズに基づいてソートします（幅が同じ場合は高さの降順）
• ペア（pair）の配列 nested を定義します
• nested の末尾に boxes[n - 1] を追加します
• i を n - 2 から始めて、i ≥ 0 の間、i を1ずつ減らしながら以下を繰り返します
  • right を nested のサイズ、left を 0 として二分探索を行います
  • left ≤ right の間、次を繰り返します
    • mid := (right + left) / 2 とします
    • nested[mid] の高さが boxes[i] の高さと一致する、または nested[mid] の幅が boxes[i] の幅以下である場合は、left := mid + 1 とします
    • それ以外の場合は、right := mid - 1 とします
  • left が nested のサイズと等しい場合、nested の末尾に boxes[i] を追加します
  • そうでない場合は、nested[left] の幅と高さを boxes[i] の値で上書きします
• 最後に nested のサイズを返します

このアルゴリズムのポイントは、「すでに外側となっている長方形」のリストを管理しながら、新しい長方形がどこに収まるかを二分探索で高速に判定する点です。収まる先が見つかれば既存のエントリを置き換え、見つからなければ新しい独立した長方形として追加します。こうすることで、最終的な nested のサイズが「残る長方形の最小数」になります。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
bool comp(const pair<int, int>& L, const pair<int, int>& R) {
    if (L.first == R.first)
        return L.second > R.second;
    return L.first < R.first;
}
int Rectangles(vector<pair<int, int>> &boxes) {
    int n = boxes.size();
    sort(boxes.begin(), boxes.end(), comp);
    vector<pair<int, int>> nested;
    nested.push_back(boxes[n - 1]);
    for (int i = n - 2; i >= 0; --i) {
        int right = nested.size() - 1, left = 0;
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nested[mid].first == boxes[i].first || nested[mid].second <= boxes[i].second)
                left = mid + 1;
            else
                right = mid - 1;
        }
        if (left == nested.size())
            nested.push_back(boxes[i]);
        else {
            nested[left].second = boxes[i].second;
            nested[left].first = boxes[i].first;
        }
    }
    return nested.size();
}
int main() {
    vector<pair<int, int>> boxes = {{30, 45}, {15,15}, {45,30},{60,75}};
    cout << Rectangles(boxes);
}

入力

{{30, 45}, {15,15}, {45,30},{60,75}}

出力

2