区間（Interval）を扱うアルゴリズム問題は、ソートと貪欲法（Greedy Algorithm）を組み合わせることで効率的に解決できる場合が多くあります。ここでは、「重複する区間の削除」「文字列の分割」「区間の統合」という3つの代表的なパターンについて解説します。

1. 無重畳区間の最小削除数

与えられた区間の集合から、重なりをなくすために削除する必要がある最小の区間数を求めます。この問題の鍵は、区間をソートした後に、どの区間を残すかを戦略的に選択することです。

まず、区間を開始位置で昇順にソートします。隣接する区間が重なっている場合、右端（終了位置）がより小さい方を残すことで、その後の区間と重なる可能性を低く抑えることができます。

#include <vector>
#include <algorithm>

class IntervalManager {
public:
    int minEraseOverlapIntervals(std::vector<std::vector<int>>& ranges) {
        if (ranges.empty()) return 0;

        // 開始位置でソート
        std::sort(ranges.begin(), ranges.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        int removeCount = 0;
        int currentEnd = ranges[0][1];

        for (size_t i = 1; i < ranges.size(); ++i) {
            // 現在の区間の開始が、前の区間の終了より前にある場合は重なり
            if (ranges[i][0] < currentEnd) {
                removeCount++;
                // より早く終わる方の区間を残す（貪欲法）
                currentEnd = std::min(currentEnd, ranges[i][1]);
            } else {
                // 重なっていない場合は基準を更新
                currentEnd = ranges[i][1];
            }
        }
        return removeCount;
    }
};

2. 同一文字を包含する区間の分割

文字列をできるだけ多くの断片に分割し、かつ各文字が特定の1つの断片にのみ現れるようにします。これは各文字の「最初に出現する位置」と「最後に出現する位置」を区間として捉え、重なる区間を統合する問題に変換できます。

#include <vector>
#include <string>
#include <algorithm>

class StringPartitioner {
public:
    std::vector<int> partitionLabels(std::string s) {
        std::vector<std::pair<int, int>> charBounds(26, {-1, -1});
        
        // 各文字の出現範囲を特定
        for (int i = 0; i < s.length(); ++i) {
            int charIdx = s[i] - 'a';
            if (charBounds[charIdx].first == -1) {
                charBounds[charIdx].first = i;
            }
            charBounds[charIdx].second = i;
        }

        // 存在する文字の区間のみを抽出してソート
        std::vector<std::pair<int, int>> sortedIntervals;
        for (const auto& p : charBounds) {
            if (p.first != -1) sortedIntervals.push_back(p);
        }
        std::sort(sortedIntervals.begin(), sortedIntervals.end());

        std::vector<int> results;
        int start = sortedIntervals[0].first;
        int end = sortedIntervals[0].second;

        for (size_t i = 1; i < sortedIntervals.size(); ++i) {
            if (sortedIntervals[i].first < end) {
                // 区間が重なっていれば拡張
                end = std::max(end, sortedIntervals[i].second);
            } else {
                // 重なりが途切れたら結果に追加
                results.push_back(end - start + 1);
                start = sortedIntervals[i].first;
                end = sortedIntervals[i].second;
            }
        }
        results.push_back(end - start + 1);
        return results;
    }
};

3. 重複する区間のマージ

複数の区間が重なっている場合、それらを1つの大きな区間に統合します。ソート済みのリストを走査しながら、現在の区間が前の区間と結合できるかどうかを判定します。

#include <vector>
#include <algorithm>

class RangeMerger {
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;
        merged.push_back(intervals[0]);

        for (size_t i = 1; i < intervals.size(); ++i) {
            auto& last = merged.back();
            // 現在の区間の開始が、マージ済み区間の末尾以下なら統合可能
            if (intervals[i][0] <= last[1]) {
                last[1] = std::max(last[1], intervals[i][1]);
            } else {
                merged.push_back(intervals[i]);
            }
        }
        return merged;
    }
};