C++である区間が別の区間を含むかどうかを判定するアルゴリズム

問題概要

2次元の区間リストが与えられます。各区間は [start, end]（開始値と終了値）の2つの値で表されます。このリストの中に、別の区間を完全に含んでいる区間が存在するかどうかを判定するのがこの問題の目的です。

たとえば、入力が [[2,4],[5,11],[5,9],[10,10]] の場合を見てみましょう。[5,11] という区間が [5,9] を含んでいるため、出力は true（真） となります。

解決のためのアプローチ

この問題は、区間を適切にソートしてから線形走査を行うことで効率的に解くことができます。具体的な手順は以下の通りです。

• まず、配列 v を「終了値の昇順」でソートします（終了値が同じ場合は開始値の降順）。
• 結果保持用の2次元配列 ret を定義します。
• v 内の各区間 it に対して、以下の処理を繰り返します。
  • ret が空の場合：it を ret の末尾に追加します。
  • ret の末尾区間の開始値が現在の区間の開始値（it[0]）以上の場合：true を返します（ある区間が別の区間を含んでいることが確定）。
  • それ以外の場合：it を ret の末尾に追加します。
• すべての区間を処理しても含む関係が見つからなければ、false を返します。

なぜこの方法で正しく判定できるのか

終了値の昇順でソートしているため、すでに処理した区間（ret の末尾）の終了値は、必ず現在の区間の終了値以下になります。この状態で処理済み区間の開始値が現在の区間の開始値以上であれば、「開始位置は現在の区間より後ろ・終了位置は前」という関係が成り立ち、現在の区間がその区間を完全に含んでいることが分かります。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool static cmp(vector<int> &a, vector<int> &b) {
        return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
    }
    bool solve(vector<vector<int>> &v) {
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> ret;
        for (auto &it : v) {
            if (ret.empty())
            ret.push_back(it);
            else if (ret.back()[0] >= it[0])
            return true;
            else
            ret.push_back(it);
        }
        return false;
    }
};
main() {
    Solution ob;
    vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
    cout << (ob.solve(v));
}

入力

{{2,4},{5,11},{5,9},{10,10}}

出力

1

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。また、空間計算量は結果保持用の配列 ret に依存し、最悪の場合で O(n) となります。区間の包含関係を効率よく判定したい場面で役立つ、シンプルかつ実用的な手法と言えるでしょう。