Terjemahan artikel ini disiapkan khusus untuk siswa dari kursus "Algoritma untuk Pengembang" .
Artikel ini adalah bagian dari seri tentang bagaimana menyelesaikan masalah algoritmik. Berdasarkan pengalaman pribadi saya, saya menemukan bahwa sebagian besar sumber daya hanya menggambarkan solusi secara detail. Penjelasan dari garis utama penalaran yang memungkinkan menemukan solusi yang efektif, sayangnya, tidak terlalu umum. Oleh karena itu, tujuan dari seri ini adalah untuk menjelaskan kemungkinan cara berpikir untuk menyelesaikan masalah dari awal.
Tantangan
Manajer hotel harus memproses pesanan reservasi N untuk musim berikutnya. Hotelnya memiliki kamar K. Informasi pemesanan berisi tanggal check-in dan tanggal check-out. Manajer ingin mencari tahu apakah ada cukup kamar di hotel untuk memenuhi permintaan.
Input data:
- Yang pertama masuk daftar dengan informasi tentang waktu kedatangan
- Kedua - daftar dengan informasi tentang waktu keberangkatan
- Ketiga - K, menunjukkan jumlah kamar
Output data:
- Nilai logis yang menunjukkan kemampuan memesan kamar
false berarti hotel tidak memiliki cukup kamar untuk pemesanan N
benar berarti hotel ini memiliki cukup kamar untuk pemesanan N.
Contoh:
Input data:
- check-in = [1, 3, 5]
- keberangkatan = [2, 6, 10]
- K = 1
Output: salah. Pada hari = 5 hotel ini memiliki 2 tamu. Tetapi kami hanya memiliki satu nomor.
Proses pengambilan keputusan
Tugas ini menarik, menurut saya, karena ada banyak cara berbeda untuk menyelesaikannya. Mari kita lihat opsinya.
Struktur yang menyimpan penghitung untuk setiap hari
Gagasan pertama mungkin bahwa kita membutuhkan struktur untuk menyimpan jumlah pesanan untuk setiap hari. Struktur ini dapat berupa larik dengan ukuran tetap (ditentukan oleh hari keberangkatan maksimum).
Input data:
- entri = [1, 3, 5]
- keberangkatan = [2, 6, 10]
- k = 1
Untuk contoh ini, ukuran array adalah 10 (karena keluar terakhir pada hari 10). Untuk mengisi larik ini, kita melihat daftar entri dan keluar dan menambah atau mengurangi penghitung hari yang sesuai. Contoh kode semu:
int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- }
Hasilnya, kami mendapatkan array berikut:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10Setelah array penuh, Anda hanya perlu melihatnya dan memeriksa apakah semua elemen tidak melebihi
k (jumlah kamar).
Pada contoh sebelumnya, jumlah kamar maksimum adalah 1. Karena pada hari ke 5 kami memiliki 2 pemesanan, kami mengembalikan
false .
Kompleksitas waktu dari solusi ini adalah O (n), di mana n adalah jumlah pemesanan, dan spasial adalah O (m), di mana m adalah hari keberangkatan maksimum. Tidak buruk dalam teori, tetapi kemungkinan akan mengalokasikan banyak memori untuk array besar, meskipun sebagian besar tidak akan digunakan.
Sebagai contoh:
Input data:
- entri = [1, 3, 5]
- keberangkatan = [2, 10000, 10]
- k = 1
Dalam hal ini, array 10 ribu bilangan bulat akan dialokasikan.
Mari kita lihat solusi lain.
Penyimpanan Koleksi Acara
Opsi apa lagi yang ada? Mari kita lihat kembali apa yang terjadi dengan struktur sebelumnya:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10Kami melihat bahwa beberapa informasi digandakan. Misalnya, antara 6 dan 9 hari jumlah pemesanan tidak berubah, karena kami tahu bahwa tidak akan terjadi apa-apa selama periode waktu ini.
Mungkinkah lebih baik jika acara disimpan saja? Mari kita ambil contoh yang sama lagi:
Input data:
- entri = [1, 3, 5]
- keberangkatan = [2, 6, 10]
Hari 1: +1 pemesanan
Hari 2: -1 pemesanan
Hari 3: +1 pemesanan
Hari 6: -1 pemesanan
Hari 5: +1 pemesanan
Hari 10: -1 pemesanan
Solusinya adalah dengan mengulangi peristiwa ini untuk menambah atau mengurangi penghitung. Jika pada titik tertentu penghitung lebih besar dari
k , kami mengembalikan
false . Namun, untuk mengulanginya, koleksi acara ini perlu disortir.
Struktur apa yang lebih baik untuk digunakan di sini? Mari kita simpulkan persyaratan kami:
- Cari untuk memeriksa apakah hari seperti itu sudah ada
- Menambahkan hari baru,
- Lihat struktur untuk beralih setiap hari yang disortir.
Bagaimana dengan menggunakan pohon pencarian biner (BST)?
Setiap node dapat direpresentasikan sebagai berikut:
class Node { int day int count Node left Node right }
Penyortiran akan dilakukan di bidang
day .
Mari kita lihat konsekuensi dari segi kompleksitas waktu:
- Cari untuk memeriksa apakah hari seperti itu sudah ada: O (log (n)) dalam kasus rata-rata, O (n) dalam kasus terburuk,
- Menambahkan hari baru: O (log (n)) dalam kasus rata-rata, O (n) dalam kasus terburuk,
- Lihat struktur untuk iterasi setiap hari yang diurutkan: O (n) menggunakan pencarian mendalam.
Karena kita harus mengulangi setiap elemen dan memasukkannya ke dalam pohon, kompleksitas algoritma adalah O (n log (n)) dalam kasus rata-rata, O (nĀ²) dalam kasus terburuk.
Pilihan lain adalah menggunakan tabel hash dan mengurutkan tombol setelah menambahkan semua acara:
- Cari untuk memeriksa apakah hari seperti itu sudah ada: O (1) dalam kasus rata-rata, O (n) dalam kasus terburuk (probabilitas tergantung pada kapasitas array asosiatif),
- Menambahkan hari baru: O (1) dalam kasus rata-rata, O (n) dalam kasus terburuk,
- Lihat struktur untuk iterasi setiap hari yang disortir: O (n log (n)) untuk kunci penyortiran dan O (n) untuk penyortiran.
Pada akhirnya, solusinya memiliki O (n log (n)) dalam case tengah (karena operasi sortir), O (nĀ²) dalam case terburuk. Solusi ini tampaknya memiliki kompleksitas yang sama dengan solusi berbasis pohon.
Mari kita lihat kemungkinan implementasi di Java menggunakan array asosiatif yang diurutkan:
public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { // Map<Integer, Integer> events = new HashMap<>(); // int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); // Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); // current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } // Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); // count if (count > k) { return false; } } return true; }
Kompleksitas spasial yang konstan
Jika kita ingin mengoptimalkan algoritme kita, kita perlu memikirkan apakah benar-benar perlu untuk menyimpan semua peristiwa ini? Tidak bisakah kita memilah-milah data pengumpulan (entri dan keluar) dan memeriksa batas reservasi dalam proses?
Sebuah solusi mungkin dilakukan, tetapi untuk ini perlu menyederhanakan data input dengan mengurutkannya terlebih dahulu.
Jika kedua koleksi diurutkan, kita dapat dengan mudah beralih ke setiap elemen menggunakan dua pointer (satu untuk pintu masuk dan yang lainnya untuk pintu keluar), dan memeriksa batasan dengan cepat.
Seperti yang Anda lihat, selama setiap iterasi kita masih perlu memeriksa minimum antara
arrivals.get(indexArrival) departures.get(indexDeparture) untuk mencari tahu pointer mana yang perlu diperbarui.
Secara umum, algoritma memiliki kompleksitas temporal dan spasial O (n log (n)) yang konstan karena operasi penyortiran.