課題の概要
互いに重複しない（overlapping な）区間のセットが、開始時間に基づいて昇順にソートされた状態で与えられます。このセットに対して、指定された新しい区間を挿入し、必要に応じて既存の区間と統合（マージ）して返すことが求められます。
結果も同様に重複せず、開始時間でソートされている状態である必要があります。
思考プロセス
この問題を解決する鍵は、与えられた既存の区間リストを、挿入対象の新しい区間との関係性に基づいて分類することにあります。単純に新しい区間をリストへ追加してから再ソートや全体マージを行う方法もありますが、すでにリストがソートされている性質を利用することで、O(N) の時間計算量で効率的に処理が可能です。
具体的には、既存の区間を以下の 3 つのカテゴリに分けて処理します。
- 新しい区間の開始位置よりも完全に左側にある区間
- 新しい区間と重複している、あるいは挟まれる区間
- 新しい区間の終了位置よりも完全に右側にある区間
重複する可能性がある中間の区間については、新しい区間の範囲を拡張しながら統合していきます。その後、左側の区間リスト、統合後の新区間、右側の区間リストを結合することで最終結果が得られます。
実装例 (C++)
class Solution {
public:
std::vector<std::vector<int>> insert(std::vector<std::vector<int>>& ranges, std::vector<int>& target) {
std::vector<std::vector<int>> result;
int n = ranges.size();
int currentIdx = 0;
// 1. 新区間の開始点より前の区間はそのまま追加
while (currentIdx < n && ranges[currentIdx][1] < target[0]) {
result.push_back(ranges[currentIdx]);
currentIdx++;
}
// 2. 重複がある区間を統合
while (currentIdx < n && ranges[currentIdx][0] <= target[1]) {
target[0] = std::min(target[0], ranges[currentIdx][0]);
target[1] = std::max(target[1], ranges[currentIdx][1]);
currentIdx++;
}
result.push_back(target);
// 3. 残りの区間を追加
while (currentIdx < n) {
result.push_back(ranges[currentIdx]);
currentIdx++;
}
return result;
}
};実装例 (Java)
class Solution {
public int[][] insert(int[][] originalIntervals, int[] incomingRange) {
List<int[]> leftSide = new ArrayList<>();
List<int[]> rightSide = new ArrayList<>();
int mergedStart = incomingRange[0];
int mergedEnd = incomingRange[1];
for (int[] interval : originalIntervals) {
// 現在の区間が新区間の終了より前なら、左側に格納
if (interval[1] < mergedStart) {
leftSide.add(interval);
}
// 現在の区間が新区間の開始より後なら、右側に格納
else if (mergedEnd < interval[0]) {
rightSide.add(interval);
}
// それ以外は重複あり、範囲を更新
else {
mergedStart = Math.min(mergedStart, interval[0]);
mergedEnd = Math.max(mergedEnd, interval[1]);
}
}
// 結果構築
List<int[]> finalList = new ArrayList<>(leftSide);
finalList.add(new int[]{mergedStart, mergedEnd});
finalList.addAll(rightSide);
return finalList.toArray(new int[finalList.size()][]);
}
}