Menjelaskan penggabungan interval
Linden Rooms perlu menggabungkan pemesanan yang tumpang tindih untuk satu ruangan. Input berisi interval setengah terbuka dalam menit bilangan bulat [start, end), dan interval yang bersebelahan harus tetap terpisah. Jelaskan sebuah algoritma dan telusuri kasus batasnya sambil berbicara dengan suara lantang.
Rubrik dan persiapanJawaban level mid mencakup apa saja · 3 pelajaran untuk persiapan
Menengah standar
- Hubungkan asumsi, metode, dan hasil: Saya memastikan setiap interval memiliki awal yang lebih kecil dari akhirnya dan semuanya untuk satu ruangan dengan basis waktu yang sama, karena aturan penggabungan bergantung pada kontrak itu. Pada interval setengah terbuka, akhir yang sama dengan awal berikutnya tidak dihitung tumpang tindih. Saya menetapkan bahwa input kosong menghasilkan output kosong.
- Uji kasus batas yang paling berpengaruh: Untuk [1,8), [2,3), [8,10) saya mempertahankan [1,8) dan [8,10), karena interval bersarang tidak bisa memperpendek akhir dan bersebelahan bukan berarti tumpang tindih. Saya juga menguji duplikat, satu interval, dan input kosong, serta menolak titik ujung yang terbalik.
- Jelaskan satu pemeriksaan validasi atau operasional yang menjadi tanggung jawab Anda: Pengurutan berbiaya O(n log n) dan pemindaian O(n); output bisa memerlukan ruang O(n) karena setiap interval mungkin terpisah. Jika input dijamin sudah terurut, saya bisa menggabungkan secara streaming, tetapi saya tetap memvalidasi urutannya atau mengandalkan kontrak yang eksplisit.