Merge Intervals

区間とは、開始点と終了点を持つ整数の範囲です。少なくとも1つの点を共有する区間はひとまとまりになり、接しているだけの区間も同様です。[1, 4] と [4, 5] は [1, 5] になります。目標は、重なり合う区間の各グループを、そのグループ全体を覆う1つの区間に置き換えることです。

ポイントは順序です。区間を開始点でソートすれば、作成中の区間と重なるものはその直後に並びます。ソート済みのリストを順にたどり、最後にマージした区間を保持します。次の開始点がその終了点以下なら終了点を延ばし、そうでなければ実際の隙間があるため、新しい区間を開始します。ソートの計算量は O(n log n) で、走査は1回です。

mergeIntervalsという名前の関数を作成してください。この関数は2つの整数配列、startsとendsを受け取り、結合した区間を返します。

ここで扱うすべての言語が入力として2次元配列を受け付けるわけではないため、区間は2つの配列として渡されます。区間iは[starts[i], ends[i]]で表され、両方の配列の長さは同じです。区間はソートされていません。

重なり合う区間のグループをすべて結合してください。端点で接するだけの区間も、重なり合っているものとして扱います。結合した区間を、開始位置の昇順にソートした2次元配列[[start, end], ...]として返してください。

たとえば、starts = [5, 1, 12, 3]とends = [7, 4, 14, 6]は、[5, 7]、[1, 4]、[12, 14]、[3, 6]を表し、これらは[[1, 7], [12, 14]]に結合されます。

制約: 1 <= starts.length == ends.length <= 10^4、0 <= starts[i] <= ends[i] <= 10^4。