Meeting Rooms II

Q: מהי סיבוכיות הזמן של Meeting Rooms II?

שני הפתרונות המהירים פועלים ב־ O(n log n) . גרסת הערימה ממיינת את הפגישות ומבצעת פעולת ערימה אחת של O(log n) לכל פגישה; גרסת שתי הרשימות מבצעת שתי פעולות מיון ומעבר אחד של O(n) . שתיהן משתמשות בזיכרון נוסף של O(n) . ספירת הפגישות המתקיימות בכל התחלה היא O(n²) .

בינוניקטעים ערימה מיון

+10

מקבלים רשימה של פגישות כשני מערכים: פגישה i נמשכת מ-starts[i] עד ends[i]. בכל חדר מתקיימת פגישה אחת בכל פעם, ופגישה יכולה להתחיל בחדר בדיוק ברגע שפגישה אחרת בו מסתיימת.

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

פונקציה

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

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

אילוצים

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
הפגישות אינן ממוינות. שתי פגישות עשויות להיות זהות.

דוגמאות

קלט: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
פלט: 3
הסבר: בזמן 4 הפגישות מ־1 עד 5, מ־2 עד 6 ומ־4 עד 8 מתקיימות כולן, ולכן צריך לפחות 3 חדרים. שלושה מספיקים: הפגישה מ־7 עד 9 משתמשת בחדר שמתפנה ב־5.

קלט: starts = [0, 2, 3]ends = [10, 3, 5]
פלט: 2
הסבר: הפגישה בין 0 ל-10 מעסיקה חדר אחד לאורך כל הזמן. הפגישה בין 2 ל-3 זקוקה לחדר שני, והפגישה בין 3 ל-5 משתמשת באותו חדר כשהוא מתפנה, כך ש-2 חדרים מספיקים.

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

שאלת המשך

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

פתרון

מספר החדרים שאתה צריך הוא המספר הגדול ביותר של פגישות שמתקיימות באותו זמן. ספירת הפגישות המתקיימות בכל שעת התחלה מוצאת אותו בזמן O(n²). מיון הופך את השאלה למעבר אחד לאורך היום: ערימת מינימום של הזמנים שבהם החדרים מתפנים, או שתי רשימות ממוינות של זמני התחלה וסיום, נותנות את התשובה בזמן O(n log n).

ספירת הפגישות שמתקיימות בכל שעת התחלה

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

האינטואיציה

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

מספר הפגישות שמתקיימות גדל רק כשפגישה מתחילה, ולכן הרגע העמוס ביותר הוא תחילתה של פגישה כלשהי. עבור כל פגישה i, סופרים את הפגישות j שעבורן starts[j] ≤ starts[i] < ends[j]: הן התחילו ועדיין לא הסתיימו. פגישה שמסתיימת בדיוק בזמן starts[i] לא נספרת, כי החדר שלה שוב פנוי באותו רגע.

בדוגמה הראשונה, בזמן 4 מתקיימות הפגישות מ־1 עד 5, מ־2 עד 6 ומ־4 עד 8: 3. בזמן 7 מתקיימות רק הפגישות מ־4 עד 8 ומ־7 עד 9: 2. המספר המרבי הוא 3.

כל אחת מ־n הפגישות סורקת את כל n הפגישות. כש־n = 5000, מדובר ב־25 מיליון בדיקות: שבריר שנייה ב־C, כמה שניות ב־Python או ב־R, ופי ארבעה יותר בכל פעם ש־n מוכפל.

אלגוריתם

עבור כל פגישה i, הגדר את running ל־0.
עבור כל פגישה j, הוסף 1 ל־running כאשר starts[j] ≤ starts[i] < ends[j].
שמור את הערך הגדול ביותר של running שראית.
החזר את הערך הגדול ביותר.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

ערימת מינימום של הזמנים שבהם החדרים מתפנים

האינטואיציה

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

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

צריך לדעת מהי שעת הפינוי המוקדמת ביותר מבין החדרים, והיא משתנה אחרי כל פגישה. ערימת מינימום שומרת שעת סיום אחת לכל חדר ומחזירה לך את הקטנה ביותר. שימוש חוזר בחדר מחליף את שעת הסיום שלו בשעת הסיום של הפגישה החדשה; פתיחת חדר מוסיפה שעת סיום חדשה לערימה. בדוגמה הראשונה, לאחר מיון לפי שעת התחלה: 1 עד 5 נותנת [5], 2 עד 6 נותנת [5, 6], 4 עד 8 נותנת [5, 6, 8], ו-7 עד 9 מוצאת את 5, שקטן מ-7 או שווה לו, ומחליפה אותו, כך שנשארת [6, 8, 9]. שלושה חדרים.

המיון עולה O(n log n), וכל פגישה מבצעת פעולת ערימה אחת בעלות O(log n). heapq של Python, ‏PriorityQueue של Java, ‏priority_queue של C++ עם greater, ‏BinaryHeap של Rust עם Reverse, ‏container/heap של Go ו-SplMinHeap של PHP מספקים לך את הערימה. בשפות האחרות שומרים אותה במערך: ההורה של האינדקס i נמצא ב-(i-1)/2, וערך עולה למעלה כל עוד הוא קטן מההורה שלו.

אלגוריתם

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

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

ממיינים את נקודות ההתחלה ואת נקודות הסיום בנפרד

האינטואיציה

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

עבור כל שעת התחלה לפי הסדר: אם היא מאוחרת או שווה ל־endTimes[ended], פגישה הסתיימה עד אז. החדר שלה מקבל את הפגישה החדשה, ו־ended מתקדם. אחרת, כל החדרים שבשימוש עדיין תפוסים, ו־rooms גדל באחד. כל שעת התחלה מנצלת לכל היותר שעת סיום אחת, בדומה לחדר שמוחזר לשימוש בערימה, ובכך מחליף שעת סיום ישנה אחת בשעת סיום חדשה.

בדוגמה הראשונה זמני ההתחלה הם 1, 2, 4, 7 וזמני הסיום הם 5, 6, 8, 9. זמני ההתחלה 1, 2 ו־4 כולם קודמים לשעת הסיום 5, ולכן rooms גדל עד 3. שעת ההתחלה 7 מאוחרת או שווה ל־5, ולכן היא משתמשת שוב בחדר הזה, ו־ended מתקדם לשעת הסיום 6. התשובה היא 3. הסימן ≥ הוא המאפשר לפגישות שנוגעות זו בזו לחלוק חדר: בדוגמה השנייה, שעת ההתחלה 12 פוגשת את שעת הסיום 12 ומשתמשת בחדר שוב.

הספירה לעולם אינה עולה על השיא האמיתי: כש־rooms גדל, שעת הסיום הבאה עדיין בעתיד, ולכן כל הפגישות שב־rooms מתקיימות באותו רגע. היא גם מגיעה לשיא, כי שעת התחלה מדלגת על פתיחת חדר רק כאשר שעת סיום אמיתית, שמתרחשת באותו זמן או לפניו, פינתה חדר. מיון פעמיים עולה O(n log n), מעבר על הרשימה עולה O(n), והעותקים הממוינים דורשים O(n) מקום.

אלגוריתם

מיין עותק של זמני ההתחלה ועותק של זמני הסיום.
הגדר את rooms ואת ended ל־0.
עבור כל זמן התחלה לפי הסדר, אם הוא שווה ל־endTimes[ended] או מאוחר ממנו, הוסף 1 ל־ended: הפגישה משתמשת בחדר שהתפנה.
אחרת, הוסף 1 ל־rooms.
החזר את rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

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

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

בדיקה של start > end במקום start ≥ end. כך פגישה לא יכולה להשתמש בחדר ברגע שהוא מתפנה, והפגישות מ־10 עד 12, מ־12 עד 14 ומ־14 עד 16 דורשות 2 חדרים במקום 1.
בדיקת החדר שפתחת לאחרונה במקום החדר שמתפנה ראשון. עבור הפגישות מ־1 עד 3, מ־2 עד 10 ומ־4 עד 6, החדר האחרון שנפתח תפוס עד 10, ולכן פותחים חדר שלישי אף שהחדר הראשון פנוי מאז 3.
בחירת המספר הגדול ביותר של פגישות שחופפות לפגישה אחת, בתוספת אחת. הפגישה מ־0 עד 10 חופפת לפגישות מ־2 עד 3 ומ־3 עד 5, אבל שתי הפגישות האלה אינן חופפות זו לזו, ולכן מספיקים 2 חדרים, לא 3.
בלבול בין שתי הגישות הממוינות. בערימה, צריך להצמיד כל שעת סיום לשעת ההתחלה שלה לפני המיון לפי שעת התחלה; הגישה עם שתי הרשימות ממיינת את שעות ההתחלה ואת שעות הסיום בנפרד בכוונה.

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

מהי סיבוכיות הזמן של Meeting Rooms II?

שני הפתרונות המהירים פועלים ב־O(n log n). גרסת הערימה ממיינת את הפגישות ומבצעת פעולת ערימה אחת של O(log n) לכל פגישה; גרסת שתי הרשימות מבצעת שתי פעולות מיון ומעבר אחד של O(n). שתיהן משתמשות בזיכרון נוסף של O(n). ספירת הפגישות המתקיימות בכל התחלה היא O(n²).

למה ערימת מינימום פותרת את בעיית Meeting Rooms II?

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

האם אפשר לפתור את Meeting Rooms II בלי ערימת מינימום?

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

האם התשובה זהה למספר הפגישות המרבי שחופפות בו-זמנית?

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

Python

def minMeetingRooms(starts, ends):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

צפוי

Meeting Rooms II

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

ספירת הפגישות שמתקיימות בכל שעת התחלה

ערימת מינימום של הזמנים שבהם החדרים מתפנים

ממיינים את נקודות ההתחלה ואת נקודות הסיום בנפרד

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

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

בעיות דומות