LeetCode 瞑想: インターバルの挿入

挿入間隔の説明は非常にわかりやすいです:

重複しない間隔の配列が与えられます。ここで、interval[i] = [start_i, end_i] は i 番目の間隔の開始と終了を表し、間隔は start_i によって昇順に並べ替えられます。また、別の間隔の開始と終了を表す間隔 newInterval = [start, end] も指定されます。

間隔が start_i によって昇順でソートされ、間隔に重複する間隔が存在しないように、newInterval を間隔に挿入します (必要に応じて重複する間隔をマージします)。

挿入後の間隔を返します。

間隔をその場で変更する必要はないことに注意してください。新しい配列を作成して返すことができます。

例:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

または:

Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]

Explanation: Because the new interval [4, 8] overlaps with [3, 5], [6, 7], [8, 10].

---

まず、結果:
を保持する結果配列の作成から始めます。

let result = [];

次に、すべての間隔を調べて、新しい間隔を現在の間隔の前後に配置するか、または、重複しているためマージする必要があるかどうかを確認する必要があります。

章の導入で見たように、一方の開始が他方の終了より厳密に大きい場合、または一方の終了が厳密に小さい場合、2 つの間隔は重なりません。相手のスタート

よりも。

これら両方のケースが false の場合、それらは重複します。

まず、newInterval が間隔の前にあるかどうかを確認できます。実際、最初にこれ (newInterval を配置するために見つけられる「最も早い」位置) を確認すると、新しく構築した結果をすぐに返すことができます。 これは貪欲な
アプローチでもあります。

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)];
  }
  /* ... */  
}

ただし、newInterval が調べている現在の間隔の後に来る場合は、現在の間隔を結果にプッシュするだけです。

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // newInterval is after interval
  else if (newInterval[0] > interval[1]) {
    result.push(interval);
  }
}

最後のオプションは、それらが重なっている場合です。その場合、2 つの間隔をマージする必要があります。間隔の最小値を新しい間隔の開始、最大値を新しい間隔の終了
として、再度 newInterval を作成できます。

for (let i = 0; i < intervals.length; i++) {
  /* ... */
  // overlapping, create newInterval
  else {
    newInterval = [
      Math.min(newInterval[0], interval[0]),
      Math.max(newInterval[1], interval[1])
    ];
  }
}

現在のループは次のようになります:

for (let i = 0; i < intervals.length; i++) {
  const interval = intervals[i];

  // newInterval is before interval
  if (newInterval[1] < interval[0]) {
    result.push(newInterval);
    return [...result, ...intervals.slice(i)] 

  // newInterval is after interval
  } else if (newInterval[0] > interval[1]) {
    result.push(interval);

  // overlapping, create newInterval
  } else {
    newInterval = [Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])];
  }
}

作成した最新の newInterval をプッシュする必要もあります。そして最後に、結果を返すだけです:

function insert(intervals: number[][], newInterval: number[]): number[][] {
  /* ... */
  result.push(newInterval);
  return result;
}

最終的に、解決策は次のようになります:

Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]

時間と空間の複雑さ

時間計算量は になります。 $O(n)$O(n) 間隔配列の各項目に対して定数演算を行うためです。空間の複雑さは次のようになります。 $O(n)$O(n) また、結果の配列を保持し、間隔の長さが増加するにつれてそのサイズも増加します。

---

次に、マージ間隔について見ていきます。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: インターバルの挿入の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。