Assign Cookies

Q: מהי סיבוכיות הזמן של Assign Cookies?

מיון שני המערכים עולה O(n log n + m log m) , והמעבר באמצעות שני מצביעים אחריו עולה O(n + m) , ולכן המיונים הם הגורם הדומיננטי. מיון במקום שומר על הזיכרון הנוסף ב־ O(1) , מלבד הזיכרון שהמיון עצמו משתמש בו.

Q: למה הבחירה החמדנית עובדת עבור Assign Cookies?

יהי k העוגייה הקטנה ביותר שמתאימה לילד הכי פחות חמדן. נניח ששיבוץ מיטבי נותן לילד הזה עוגייה אחרת. נחליף: הילד יקבל את k , ומי שקיבל את k יקבל את העוגייה האחרת, שגדולה לפחות כמו k , ולכן גם הוא יישאר שבע. המספר לא משתנה, ולכן שיבוץ מיטבי יכול תמיד להתחיל בבחירה החמדנית, ואותו טיעון חוזר על עצמו עבור הילדים והעוגיות שנותרו.

קלאלגוריתם חמדן מיון

+10

לכל ילד i יש גורם חמדנות g[i]: גודל העוגייה הקטן ביותר שישמח אותו. לכל עוגייה j יש גודל s[j]. ילד מרוצה כשהוא מקבל עוגייה אחת שגודלה לפחות כגורם החמדנות שלו. כל ילד מקבל לכל היותר עוגייה אחת, וכל עוגייה ניתנת לכל היותר לילד אחד. החזר את המספר הגדול ביותר של ילדים שתוכל לשמח.

פונקציה

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

ginteger-array: גורם החמדנות של כל ילד, גודל העוגייה הקטן ביותר שהוא מקבל
sinteger-array: הגודל של כל עוגייה
מחזירהinteger: המספר המרבי של הילדים שכל אחד מהם יכול לקבל עוגייה שגודלה לפחות כגורם החמדנות שלו

אילוצים

1 ≤ g.length, s.length ≤ 5000
1 ≤ g[i], s[j] ≤ 10⁵
לשני המערכים עשויים להיות אורכים שונים, ואף אחד מהם אינו ממוין.

דוגמאות

קלט: g = [4, 2, 7]s = [3, 5, 1, 2]
פלט: 2
הסבר: לאחר המיון, הילדים רוצים 2, 4 ו־7, והעוגיות הן 1, 2, 3 ו־5. עוגייה 2 מאכילה את הילד שרוצה 2, ועוגייה 5 מאכילה את הילד שרוצה 4. לא נשארת עוגייה שמספיקה ל־7, ולכן התשובה היא 2.

+16 בדיקות נסתרות בשליחה

שאלת המשך

מה אם לכל ילד יש גם עוגייה בגודל המרבי שהוא מוכן לקבל, כך שכל עוגייה מתאימה רק לטווח מסוים? לאיזה ילד שמחכה יש לתת כל עוגייה במקרה כזה?

פתרון

השאלה היא איזה ילד צריך לקבל איזו עוגייה. בדיקת כל ההתאמות האפשריות יוצרת מספר עצום של אפשרויות, אבל כלל חמדני אחד פותר את העניין: קודם משרתים את הילד הכי פחות חמדן, ונותנים לו את העוגייה הקטנה ביותר שמתאימה לו. אחרי שממיינים את שני המערכים, הכלל הזה הופך לסריקה אחת עם שני מצביעים.

העוגייה הקטנה ביותר שמתאימה לכל ילד

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

עבור על הילדים מהפחות חמדנים לחמדנים ביותר. עבור כל אחד מהם, בדוק את כל העוגיות שעדיין לא נעשה בהן שימוש ובחר את הקטנה ביותר שגדולה מספיק. אם אף עוגייה לא מתאימה, הילד נשאר רעב. בדוגמה הראשונה הילדים רוצים 2, 4 ו-7: הילד שרוצה 2 מקבל עוגייה בגודל 2, הילד שרוצה 4 מקבל עוגייה בגודל 5, ולא נשארת עוגייה עבור הילד שרוצה 7.

למה לבחור בעוגייה הקטנה ביותר שמתאימה? עוגייה גדולה יותר יכולה להאכיל כל ילד שהעוגייה הקטנה יותר יכולה להאכיל, וגם ילדים נוספים. חלוקת העוגייה הקטנה ביותר שמתאימה משאירה את העוגיות הגדולות יותר לילדים החמדנים יותר שמגיעים אחר כך, כך שאף פעם לא תפסיד ילד שיכולת להאכיל.

המחיר הוא החיפוש. כל אחד מ-n הילדים סורק את כל m העוגיות, ולכן כאשר n = m = 5000 מדובר ב-25 מיליון בדיקות, וזה איטי מדי עבור המבחנים הגדולים ביותר.

אלגוריתם

מיינו את גורמי החמדנות מהקטן לגדול.
נהלו דגל עבור כל עוגייה שמציין אם נעשה בה שימוש.
עבור כל ילד, סרקו את כל העוגיות וזכרו את העוגייה הקטנה ביותר שלא נעשה בה שימוש, שגודלה לפחות כגודל החמדנות של הילד.
אם מצאתם עוגייה כזאת, סמנו אותה כמשומשת וספרו את הילד כמרוצה.
החזירו את המספר.

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

מיינו את שניהם והשתמשו בשני מצביעים

האינטואיציה

הסריקה שלמעלה מחפשת שוב ושוב את העוגייה הקטנה ביותר שמתאימה. מיין גם את העוגיות, והחיפוש הזה נעלם: גודל העוגיות עולה, ולכן פוגשים קודם את העוגייה הקטנה ביותר שמתאימה.

עבור על העוגיות מהקטנה לגדולה, והשאר מצביע אחד, child, על הילד הכי פחות חמדן שעדיין ממתין. אם העוגייה גדולה או שווה ל־g[child], הילד הזה מקבל עוגייה והמצביע עובר לילד הבא. אם היא קטנה יותר, היא קטנה יותר גם מכל ילד שעדיין ממתין, כי הם ממוינים, ולכן העוגייה חסרת תועלת וממשיכים הלאה.

בדוגמה הראשונה העוגיות הממוינות הן 1, 2, 3, 5 והחמדנויות הממוינות הן 2, 4, 7. עוגייה 1 קטנה מדי בשביל 2. עוגייה 2 מאכילה את הילד שרוצה 2. עוגייה 3 קטנה מדי בשביל 4. עוגייה 5 מאכילה את הילד שרוצה 4. המצביע נעצר על 2, וזו התשובה.

כל מצביע מתקדם רק קדימה, לכן המעבר הוא O(n + m) ושתי פעולות המיון הן שקובעות את זמן הריצה. מיון במקום אינו דורש מערכים נוספים.

אלגוריתם

מיינו את g ואת s בסדר עולה.
הגדירו child = 0, הילד הפחות בררן ביותר שעדיין ממתין.
עבור כל עוגייה, מהקטנה לגדולה: אם child עדיין בתוך g והעוגייה גדולה או שווה ל-g[child], הוסיפו 1 ל-child.
החזירו את child, מספר הילדים שקיבלו עוגייה.

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

מלכודות ומקרי קצה

רוב התשובות השגויות נובעות מהתאמה בסדר הלא נכון או מהזזת המצביע הלא נכון.

נותנים לילד עוגייה גדולה יותר מזו שהוא צריך. עם g = [1, 2] ועם s = [1, 3], מתן עוגייה 3 לילד שרוצה 1 משאיר את הילד שרוצה 2 רעב, ואילו ההתאמה הנכונה מאכילה את שניהם.
מקדמים את המצביע של הילד כשהעוגייה קטנה מדי. הילד עדיין צריך עוגייה; העוגייה היא זו שאינה מועילה.
שוכחים לבדוק את הגבול עבור המצביע של הילד. אחרי שכל הילדים קיבלו עוגייה, אסור שהעוגיות שנותרו יקראו מעבר לסוף של g.
משווים באמצעות > במקום ≥. עוגייה שגודלה בדיוק כגודל גורם החמדנות מספיקה.
ממיינים מספרים כטקסט. ב-JavaScript, sort() ללא פונקציית השוואה מציב את 10 לפני 9.

שאלות נפוצות4

מהי סיבוכיות הזמן של Assign Cookies?

מיון שני המערכים עולה O(n log n + m log m), והמעבר באמצעות שני מצביעים אחריו עולה O(n + m), ולכן המיונים הם הגורם הדומיננטי. מיון במקום שומר על הזיכרון הנוסף ב־O(1), מלבד הזיכרון שהמיון עצמו משתמש בו.

למה הבחירה החמדנית עובדת עבור Assign Cookies?

יהי k העוגייה הקטנה ביותר שמתאימה לילד הכי פחות חמדן. נניח ששיבוץ מיטבי נותן לילד הזה עוגייה אחרת. נחליף: הילד יקבל את k, ומי שקיבל את k יקבל את העוגייה האחרת, שגדולה לפחות כמו k, ולכן גם הוא יישאר שבע. המספר לא משתנה, ולכן שיבוץ מיטבי יכול תמיד להתחיל בבחירה החמדנית, ואותו טיעון חוזר על עצמו עבור הילדים והעוגיות שנותרו.

האם אפשר להתחיל דווקא מהילד החמדן ביותר?

כן. מיין את שני המערכים, ואז עבור מהעוגייה הגדולה ביותר ומהילד החמדן ביותר: אם העוגייה הגדולה ביותר שנותרה מתאימה לילד החמדן ביותר שנותר, תן אותה לילד והזז את שני המצביעים; אם לא, שום עוגייה לא תוכל להשביע את הילד הזה, אז דלג עליו. כך מתקבל אותו מספר ובאותו זמן.

האם Assign Cookies היא בעיית תכנות דינמי?

לא. טיעון החלפה מראה שהבחירה החמדנית תמיד בטוחה, ולכן מספיק למיין ולעבור פעם אחת, ב-O(n log n + m log m). טבלה על פני שני המערכים הממוינים, שממלאים כמו טבלת תת-רצף משותף ארוך ביותר, מוצאת גם היא את התשובה, אבל היא עולה O(n × m) זמן עבור אותה תוצאה.

Python

def findContentChildren(g, s):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

קלט

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

צפוי