C++で他のN個の区間すべてを包含する区間を見つける方法

問題の概要

N個の区間が与えられ、それぞれ左端の値Lと右端の値Rを持っているとします。この中から、他のN-1個の区間をすべて完全に包含している区間を見つけ、その0始まりのインデックスを出力してください。そのような区間が存在しない場合は-1を表示します。

例えば、L = [2, 4, 3, 1]、R = [4, 6, 7, 9] の場合、出力は3になります。これは、インデックス3にある区間（1〜9）が、他のすべての区間の要素を包含していることを意味します。

解法のアプローチ

すべてのLとRの値が互いに異なるという前提を利用します。まず、最も小さいLを持つ区間と、最も大きいRを持つ区間をそれぞれ特定します。この2つが同じ区間であれば、残りのすべての区間はその区間の内部に収まっていることになります。もし異なる区間であれば、すべての区間を包含する区間は存在しないため、-1を返します。

アルゴリズムの手順

1. 最小のLを持つインデックスと、最大のRを持つインデックスを初期化します。
2. 配列を一度走査し、最小Lと最大Rに対応するインデックスを更新していきます。
3. 両方のインデックスが一致していればそのインデックスを返し、一致しなければ-1を返します。

C++での実装例

#include<iostream>
using namespace std;

// すべての区間を包含する区間のインデックスを返す関数
int findCoveringRange(int L[], int R[], int n) {
    int minLIndex = 0;  // 最小のLを持つ区間のインデックス
    int maxRIndex = 0;  // 最大のRを持つ区間のインデックス

    for (int i = 1; i < n; i++) {
        if (L[i] < L[minLIndex])
            minLIndex = i;
        if (R[i] > R[maxRIndex])
            maxRIndex = i;
    }

    // 最小Lと最大Rが同じ区間なら、その区間がすべてを包含する
    if (minLIndex == maxRIndex)
        return minLIndex;

    return -1;  // そのような区間は存在しない
}

int main() {
    int L[] = {2, 4, 3, 1};
    int R[] = {4, 6, 7, 9};
    int n = sizeof(L) / sizeof(L[0]);

    int result = findCoveringRange(L, R, n);
    cout << result << endl;

    return 0;
}

出力

3

コードの解説

このプログラムでは、まず配列LとRを走査しながら、最小のLを持つ区間のインデックス（minLIndex）と最大のRを持つ区間のインデックス（maxRIndex）を追跡します。サンプル入力の場合、最小のLである1はインデックス3に、最大のRである9もインデックス3に存在するため、両者は一致します。したがって、インデックス3の区間[1, 9]が他のすべての区間を包含していると判定され、3が出力されます。

もし最小Lと最大Rが異なる区間に属していた場合、どの単一の区間も全体を覆うことができないため、関数は-1を返します。

計算量

配列を一度だけ走査するため、時間計算量はO(n)、追加のメモリは定数個の変数のみで済むため、空間計算量はO(1)と非常に効率的です。