Meditasi LeetCode: Selang Sisip

Perihalan untuk Selang Sisip cukup jelas:

Anda diberikan tatasusunan selang selang tidak bertindih di mana selang[i] = [start_i, end_i] mewakili permulaan dan penghujung selang ke-i dan selang diisih dalam tertib menaik mengikut start_i. Anda juga diberikan selang newInterval = [mula, tamat] yang mewakili permulaan dan akhir selang lain.

Masukkan newInterval ke dalam selang supaya selang masih diisih dalam tertib menaik mengikut start_i dan selang masih tidak mempunyai sebarang selang bertindih (gabungkan selang bertindih jika perlu).

Selang balik selepas sisipan.

Perhatikan bahawa anda tidak perlu mengubah suai selang di tempatnya. Anda boleh membuat tatasusunan baharu dan mengembalikannya.

Contohnya:

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

Atau:

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].

---

Kita boleh mulakan dengan mencipta tatasusunan hasil untuk disimpan, baik, hasilnya:

let result = [];

Kemudian, melalui semua selang, kita perlu menyemak sama ada kita perlu meletakkan selang baharu sebelum atau selepas selang semasa, atau, jika ia bertindih dan oleh itu perlu digabungkan.

Seperti yang telah kita lihat dalam pengenalan bab, dua selang jangan bertindih jika permulaan satu lebih besar daripada hujung yang lain, atau, jika hujung satu kurang sama sekali daripada permulaan yang lain.

Apabila kedua-dua kes itu palsu, ia bertindih.

Pertama, kita boleh menyemak sama ada newInterval datang sebelum selang. Malah, jika kami mula-mula menyemak ini (kedudukan "paling awal" yang kami dapati untuk meletakkan newInterval), kami boleh kembali serta-merta dengan hasil kami yang baru dibina.
Ini juga pendekatan tamak.

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)];
  }
  /* ... */  
}

Walau bagaimanapun, jika newInterval datang selepas selang semasa yang kami lihat, kami hanya boleh menolak selang semasa ke hasil kami:

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

Pilihan terakhir ialah apabila ia bertindih, dalam kes itu, kita perlu menggabungkan dua selang. Kita boleh mencipta newInterval sekali lagi dengan nilai minimum selang sebagai mula dan nilai maksimum selang itu sebagai akhir selang baharu:

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])
    ];
  }
}

Gelung kami pada masa ini kelihatan seperti ini:

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])];
  }
}

Kami juga perlu menolak Interval baharu terbaharu yang kami buat. Dan, pada akhirnya, kita hanya boleh mengembalikan hasilnya:

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

Akhir sekali, penyelesaiannya kelihatan seperti ini:

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

Kerumitan masa dan ruang

Kerumitan masa ialah $O(n)$O(n) kerana kami melakukan operasi berterusan untuk setiap item dalam tatasusunan selang. Kerumitan ruang akan menjadi $O(n)$O(n) serta kami menyimpan tatasusunan hasil dan saiznya akan meningkat apabila panjang selang bertambah.

---

Seterusnya, kita akan lihat pada Selang Gabungan. Sehingga itu, selamat mengekod.

Atas ialah kandungan terperinci Meditasi LeetCode: Selang Sisip. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!