Assign Cookies

Q: Berapa kompleksitas waktu dari Assign Cookies?

Pengurutan kedua array membutuhkan O(n log n + m log m) , dan penelusuran dengan dua pointer setelahnya membutuhkan O(n + m) , jadi pengurutanlah yang paling besar biayanya. Pengurutan di tempat menjaga penggunaan ruang tambahan tetap O(1) , selain ruang yang digunakan oleh proses pengurutan itu sendiri.

Q: Mengapa pilihan greedy berhasil untuk Assign Cookies?

Misalkan k adalah kue terkecil yang cukup untuk anak yang paling tidak serakah, dan anggap penugasan optimal memberikan anak itu kue lain. Tukar: anak itu mengambil k , dan siapa pun yang mendapat k mengambil kue yang lain, yang ukurannya setidaknya sama besar, sehingga keduanya tetap kenyang. Jumlahnya tidak berubah, dan argumen ini diulangi untuk anak-anak lainnya.

MudahGreedy Pengurutan

+10

Setiap anak i memiliki faktor kerakusan g[i]: ukuran kue terkecil yang membuat mereka senang. Setiap kue j memiliki ukuran s[j]. Seorang anak merasa puas saat mendapat satu kue yang ukurannya setidaknya sebesar faktor kerakusannya. Setiap anak mendapat paling banyak satu kue, dan setiap kue diberikan kepada paling banyak satu anak. Kembalikan jumlah terbesar anak yang bisa kamu buat merasa puas.

Fungsi

findContentChildren(g: integer-array, s: integer-array) → integer

ginteger-array: faktor keserakahan setiap anak, ukuran kue terkecil yang mereka terima
sinteger-array: ukuran setiap cookie
Mengembalikaninteger: jumlah anak terbanyak yang masing-masing bisa mendapatkan kue setidaknya sebesar faktor keserakahannya

Batasan

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
Kedua array mungkin memiliki panjang yang berbeda, dan keduanya tidak diurutkan.

Contoh

Input: g = [4, 2, 7]s = [3, 5, 1, 2]
Output: 2
Penjelasan: Setelah diurutkan, anak-anak menginginkan 2, 4, dan 7. Kue 2 diberikan kepada anak yang menginginkan 2, dan kue 5 kepada anak yang menginginkan 4. Tidak ada kue yang cukup untuk anak yang menginginkan 7, jadi jawabannya adalah 2.

Pertanyaan lanjutan

Bagaimana jika setiap anak juga memiliki ukuran kue terbesar yang bersedia mereka terima, sehingga sebuah kue hanya cocok dalam rentang tertentu? Lalu, kue mana yang harus diberikan kepada setiap anak yang sedang menunggu?

Solusi

Mencoba setiap pasangan anak dan cookie akan menghasilkan terlalu banyak kemungkinan, tetapi satu aturan greedy bisa menyelesaikannya: layani anak yang paling tidak serakah terlebih dahulu, dengan cookie terkecil yang cukup. Setelah mengurutkan kedua array, aturan itu menjadi satu penelusuran dengan dua pointer.

Kue terkecil yang cocok untuk setiap anak

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Urutkan anak-anak dari yang paling tidak rakus hingga yang paling rakus, lalu berikan kepada masing-masing anak kue terkecil yang belum digunakan dan cukup besar. Kue yang lebih besar dapat memberi makan setiap anak yang dapat diberi makan oleh kue yang lebih kecil. Jadi, dengan memberikan kue terkecil yang cukup, kue yang lebih besar tetap tersedia untuk anak-anak yang lebih rakus berikutnya.

Setiap n anak memeriksa semua m kue: dengan n = m = 5000, jumlahnya 25 juta pemeriksaan.

Algoritma

Urutkan faktor kerakusan dari yang terkecil hingga terbesar.
Simpan penanda untuk setiap kue yang menunjukkan apakah kue tersebut sudah digunakan.
Untuk setiap anak, periksa semua kue dan ingat kue terkecil yang belum digunakan dan ukurannya setidaknya sama dengan faktor kerakusan anak tersebut.
Jika kamu menemukan kue, tandai kue tersebut sebagai sudah digunakan dan hitung anak itu sebagai puas.
Kembalikan jumlahnya.

def findContentChildren(g, s):
    used = [False] * len(s)
    fed = 0
    for need in sorted(g):  # least greedy child first
        best = -1
        for j in range(len(s)):
            if not used[j] and s[j] >= need and (best == -1 or s[j] < s[best]):
                best = j
        if best != -1:
            used[best] = True
            fed += 1
    return fed

Urutkan keduanya dan gunakan dua pointer

Intuisi

Urutkan juga cookie, lalu kamu akan menemui cookie terkecil yang cocok terlebih dahulu. Telusuri cookie dari yang terkecil hingga terbesar dengan satu penunjuk, child, pada anak yang paling tidak serakah dan masih menunggu. Cookie yang nilainya setidaknya g[child] dapat diberikan kepada anak itu dan menggeser penunjuk. Cookie yang lebih kecil juga lebih kecil daripada tingkat keserakahan setiap anak yang masih menunggu, jadi cookie itu tidak berguna.

Pada contoh pertama, cookie 1 terlalu kecil untuk anak yang menginginkan 2, cookie 2 diberikan kepada anak yang menginginkan 2, cookie 3 terlalu kecil untuk anak yang menginginkan 4, dan cookie 5 diberikan kepada anak yang menginginkan 4. Penunjuk berhenti di 2.

Setiap penunjuk hanya bergerak maju, jadi penelusurannya memerlukan O(n + m), dan kedua proses pengurutan menjadi bagian yang paling memakan waktu.

Algoritma

Urutkan g dan s dari nilai terkecil ke terbesar.
Tetapkan child = 0, anak yang paling tidak serakah dan masih menunggu.
Untuk setiap kuki, mulai dari yang terkecil: jika child masih berada dalam g dan kuki tersebut setidaknya sebesar g[child], tambahkan 1 ke child.
Kembalikan child, jumlah anak yang diberi makan.

def findContentChildren(g, s):
    g.sort()
    s.sort()
    child = 0  # the least greedy child still waiting
    for size in s:  # smallest cookie first
        if child < len(g) and size >= g[child]:
            child += 1
    return child

Jebakan dan kasus tepi

Memberikan anak kue yang lebih besar daripada yang dibutuhkannya. Dengan g = [1, 2] dan s = [1, 3], memberikan kue 3 kepada anak yang menginginkan 1 membuat anak yang menginginkan 2 kelaparan.
Memajukan penunjuk anak saat kuenya terlalu kecil. Anak itu masih membutuhkan kue, kuenya yang tidak berguna.
Melewatkan pemeriksaan batas pada penunjuk anak. Dengan g = [1] dan s = [1, 2], kue 2 mengakses data melewati akhir g.
Membandingkan dengan >, bukan ≥. Kue yang ukurannya sama persis dengan faktor kerakusan sudah cukup.
Mengurutkan angka sebagai teks. Di JavaScript, sort() tanpa pembanding menempatkan 10 sebelum 9.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari Assign Cookies?

Pengurutan kedua array membutuhkan O(n log n + m log m), dan penelusuran dengan dua pointer setelahnya membutuhkan O(n + m), jadi pengurutanlah yang paling besar biayanya. Pengurutan di tempat menjaga penggunaan ruang tambahan tetap O(1), selain ruang yang digunakan oleh proses pengurutan itu sendiri.

Mengapa pilihan greedy berhasil untuk Assign Cookies?

Misalkan k adalah kue terkecil yang cukup untuk anak yang paling tidak serakah, dan anggap penugasan optimal memberikan anak itu kue lain. Tukar: anak itu mengambil k, dan siapa pun yang mendapat k mengambil kue yang lain, yang ukurannya setidaknya sama besar, sehingga keduanya tetap kenyang. Jumlahnya tidak berubah, dan argumen ini diulangi untuk anak-anak lainnya.

Bisakah kamu memulai dari anak yang paling serakah?

Ya. Urutkan kedua array, lalu mulai dari kue terbesar dan anak yang paling rakus. Jika kue terbesar yang tersisa cukup untuk anak paling rakus yang tersisa, berikan kue itu kepadanya dan geser kedua pointer. Jika tidak, tidak ada kue yang bisa diberikan kepada anak itu, jadi lewati anak tersebut. Cara ini menghasilkan jumlah yang sama dalam waktu yang sama.

def findContentChildren(g, s):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

g = [4, 2, 7]
s = [3, 5, 1, 2]

Output yang diharapkan