まず、区間たちを \(L\) の小さい順にソートしておきます。その後、区間をその順に見ていき、適宜区間を追加したり併合したりしていきます。具体的には、次のようにします。（直前の区間を \([x, y)\)、今見ている区間を \([l, r)\) と書きます）

• 直前の区間がない、または直前の区間と併合できない（つまり、\(y < l\) である）場合：今見ている区間を追加する。

• それ以外の場合：直前の区間と併合する。具体的には、次のようにする。

  • 今見ている区間が直前の区間に完全に含まれている（つまり、\(r \leq y\) である）場合：何もしない。
  • それ以外の場合：直前の区間を伸ばす（つまり、\(y \leftarrow r\) とする）。

たとえば \([1, 2), [2, 5), [3, 4), [6, 7)\) という入力の場合、次のように動作します。

• \([1, 2)\) を見る。最初は直前の区間がないので、\([1, 2)\) を追加する。

• \([2, 5)\) を見る。直前の区間 \([1, 2)\) と併合できるので、併合する。直前の区間に完全に含まれてはいないので、直前の区間を伸ばして \([1, 5)\) にしている。

• \([3, 4)\) を見る。直前の区間 \([1, 5)\) と併合できるので、併合する。直前の区間に完全に含まれているので、何もしていない。

• \([6, 7)\) を見る。直前の区間 \([1, 5)\) と併合できないので、\([6, 7)\) を追加する。

• 答えは \([1, 5), [6, 7)\) とわかる。

計算量はソートがボトルネックで \(O(N \log N)\) です。vector の末尾への追加が（任意位置への挿入と異なり）定数時間でできることに注意してください。

C++ による実装例：

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<pair<int, int>> LR(N);
  for (int i = 0; i < N; i++)
  {
    int l, r;
    cin >> l >> r;
    LR[i] = make_pair(l, r); // LR[i] = {l, r}; とも書ける
  }
  
  // L の小さい順にソート
  // pair 型は first → second の順で見てソートされるので、単純に sort を使えばよい
  // なお、second の小さい順にソート などする必要がある場合、比較関数 というものを用いるとよい (詳細は割愛)
  sort(LR.begin(), LR.end());

  vector<int> X, Y; // 答えを格納する配列
  for (int i = 0; i < N; i++) // i が必要ない場合、for (auto [l, r] : LR) と書くと、次の l, r を LR[i] から取ってくる行が要らなくなって簡潔に書ける
  {
    int l = LR[i].first, r = LR[i].second; // auto [l, r] = LR[i]; とも書ける
    if (X.empty() || Y.back() < l) // 追加する
    {
      X.push_back(l);
      Y.push_back(r);
    }
    else // 併合する
    {
      if (Y.back() < r)
        Y.back() = r;
      // 実はこの部分の処理は Y.back() = max(Y.back(), r); とも書ける
    }
  }

  for (int i = 0; i < (int)X.size(); i++)
    cout << X[i] << " " << Y[i] << endl;
}

このような実装の方針は ランレングス圧縮 や、ソート済み配列の重複を消す操作などにも活用できます。

類題：

• AtCoder Beginner Contest 143 C - Slimes

• AtCoder Beginner Contest 240 D - Strange Balls