🔄 Merge Intervals Algorithm

区間マージアルゴリズムの詳細解析

📋 アルゴリズム概要

目的: 重複する区間をマージして、重複のない区間リストを作成

戦略: ソート → 順次比較・マージ

キーポイント: 区間の開始点でソートすることで、線形時間でのマージが可能

💻 TypeScript実装

/**
 * 重複する区間をマージして、重複のない区間の配列を返す
 * @param intervals - 区間の配列。各区間は[start, end]の形式
 * @returns マージされた重複のない区間の配列
 * 
 * 時間計算量: O(n log n) - ソート処理が支配的
 * 空間計算量: O(1) - 入力配列を直接変更するため（ソートを除く）
 */
function merge(intervals: number[][]): number[][] {
    // 空配列または単一要素の場合はそのまま返す
    if (intervals.length <= 1) {
        return intervals;
    }
    
    // 区間を開始点でソート
    intervals.sort((a: number[], b: number[]): number => a[0] - b[0]);
    
    // 結果を格納する配列（最初の区間から開始）
    const merged: number[][] = [intervals[0]];
    
    // 2番目の区間から順次処理
    for (let i: number = 1; i < intervals.length; i++) {
        const current: number[] = intervals[i];
        const lastMerged: number[] = merged[merged.length - 1];
        
        // 現在の区間が直前のマージ済み区間と重複している場合
        if (current[0] <= lastMerged[1]) {
            // 終了点を更新してマージ
            lastMerged[1] = Math.max(lastMerged[1], current[1]);
        } else {
            // 重複していない場合は新しい区間として追加
            merged.push(current);
        }
    }
    
    return merged;
}

📊 ステップバイステップ解析

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

1

初期化

2

ソート

3

処理開始

4

マージ

5

完了

1初期化チェック

if (intervals.length <= 1) {
    return intervals;
}

処理: 空配列または単一要素の場合の早期リターン

効果: 不要な処理を避けてパフォーマンス向上

2ソート処理

intervals.sort((a: number[], b: number[]): number => a[0] - b[0]);

処理: 区間を開始点で昇順ソート

時間計算量: O(n log n)

ソート前:
[1,3]
[2,6]
[8,10]
[15,18]
↓
ソート後:
[1,3]
[2,6]
[8,10]
[15,18]

3初期設定

const merged: number[][] = [intervals[0]];

処理: 最初の区間をマージ結果に追加

空間計算量: O(k) - kはマージ後の区間数

merged初期化:
[1,3]

4メインループ処理

for (let i: number = 1; i < intervals.length; i++) {
    const current: number[] = intervals[i];
    const lastMerged: number[] = merged[merged.length - 1];
    
    if (current[0] <= lastMerged[1]) {
        // マージ処理
        lastMerged[1] = Math.max(lastMerged[1], current[1]);
    } else {
        // 新規追加
        merged.push(current);
    }
}

重複判定条件: current[0] <= lastMerged[1]

マージ処理: Math.max(lastMerged[1], current[1])

⚡ 計算量分析

🕒 時間計算量: O(n log n)

  • ソート処理: O(n log n) - 支配的な要因
  • メインループ: O(n) - 各要素を1回ずつ処理
  • 全体: O(n log n) + O(n) = O(n log n)

💾 空間計算量: O(1)

  • 入力変更: 元の配列を直接ソート（追加メモリ不要）
  • 結果配列: 最悪でもO(n)、通常はより少ない
  • 補助変数: O(1) - 定数個の変数のみ

🚀 最適化ポイント

1in-place操作

元の配列を直接変更することで、追加のメモリ使用量を最小化

2早期終了

単純なケース（空配列・単一要素）の早期リターンでパフォーマンス向上

3効率的なマージ

Math.maxを使用した最適な終了点更新

4TypeScript型安全性

コンパイル時の型チェックでランタイムエラーを防止