区間のマージ - tanakakenji/Rinko GitHub Wiki

問題文

整数の区間を表す配列のベクトルが与えられます。重複する区間をマージして、重複のない区間のベクトルを返してください。

入力: intervals = [[1,3],[2,6],[8,10],[15,18]]

出力: [[1,6],[8,10],[15,18]]

説明: 区間 [1,3] と [2,6] が重複しているため、[1,6] にマージされます。

解答 (C++)

#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    std::vector<std::vector<int>> merge(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        // 区間を開始時点でソート
        std::sort(intervals.begin(), intervals.end());
        
        std::vector<std::vector<int>> merged;
        for (const auto& interval : intervals) {
            // マージされた区間がない、または現在の区間の開始が前の区間の終了より後の場合
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                // 重複がある場合、前の区間の終了を更新
                merged.back()[1] = std::max(merged.back()[1], interval[1]);
            }
        }
        
        return merged;
    }
};

// テスト用のメイン関数
int main() {
    Solution sol;
    std::vector<std::vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}};
    auto result = sol.merge(intervals);
    
    // 結果の出力
    for (const auto& interval : result) {
        std::cout << "[" << interval[0] << "," << interval[1] << "] ";
    }
    std::cout << std::endl;
    
    return 0;
}

解説

  1. 配列のソートの重要性:

    • C++では、std::sort関数を使用して区間をソートしています。
    • デフォルトで、std::vector<std::vector<int>>は最初の要素（開始時点）で比較されるため、カスタムの比較関数は不要です。

  2. ソートの影響:

    • Pythonの場合と同様、ソートにより元の配列の順序は失われますが、この問題では許容されます。

  3. アルゴリズムの流れ:

    • ソート後、新しいベクター merged に結果を格納していきます。
    • 各区間を順に見て、前の区間と重複がある場合はマージし、ない場合は新しい区間として追加します。

  4. C++特有の考慮点:

    • std::vectorを使用して動的配列を扱います。
    • 範囲ベースのfor文（for (const auto& interval : intervals)）を使用して、より読みやすく効率的なコードを書いています。

  5. 時間複雑度:

    • std::sortは平均的に O(n log n) の時間複雑度を持ちます（nは区間の数）。
    • その後の走査は O(n) です。
    • したがって、全体の時間複雑度は O(n log n) となります。

  6. 空間複雑度:

    • 新しいベクター merged を作成するので、最悪の場合 O(n) の追加空間が必要です。

  7. C++でのパフォーマンス最適化:

    • 必要に応じて、merged ベクターの容量を事前に確保することで、再割り当てのオーバーヘッドを減らせる可能性があります（merged.reserve(intervals.size());）。
    • 入力が既にソートされていることが保証されている場合、ソートのステップをスキップでき、全体の時間複雑度を O(n) に改善できます。

  8. 面接での注意点:

    • C++を使用する場合、メモリ管理やポインタの扱いについて質問される可能性があります。この解答ではスマートポインタやメモリの動的確保を避けていますが、それらの知識も重要です。
    • std::vectorやstd::sortなどの標準ライブラリの使用は、効率的で読みやすいコードを書く能力を示すのに役立ちます。

この C++ の実装は、配列（ベクター）のソートが問題解決にどのように役立つかを示す良い例です。言語が変わっても、アルゴリズムの本質と効率性は同じであることを理解することが重要です。

⚠️ **GitHub.com Fallback** ⚠️