Minimum Platforms

Q: מהי סיבוכיות הזמן של בעיית מספר הרציפים המינימלי?

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

Q: במה שונה בעיית מינימום הרציפים מבעיית חדרי הישיבות II?

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

Q: האם אפשר לפתור את בעיית מספר הרציפים המינימלי בלי למיין?

כן, כי כל שעה מתאימה לשעה קבועה בשעון. מַדֵּד 2401 מונים לפי מספר HHMM , הוסף 1 בכל הגעה והפחת 1 ב- departure + 1 . הסכום המצטבר הגדול ביותר הוא התשובה: זמן של O(n + 2400) . אינדקסים כמו 1260 עד 1299 אינם שעות בשעון ולא מתרחשת בהם הגעה, ולכן הם לעולם לא קובעים שיא.

בינונימיון אלגוריתם חמדן שני מצביעים

+10

בתחנה יש לוח זמנים ליום אחד: רכבת i מגיעה בשעה arrival[i] ויוצאת בשעה departure[i]. השעות הן מספרים בפורמט HHMM, כלומר השעה ללא הנקודתיים, כך ש-930 פירושו 09:30.

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

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

פונקציה

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: שעת ההגעה של כל רכבת, כמספר בפורמט HHMM
departureinteger-array: שעת היציאה של כל רכבת, כמספר בפורמט HHMM; departure[i] שייך ל־arrival[i]
מחזירהinteger: המספר הגדול ביותר של רכבות בתחנה באותה דקה, שהוא מספר הרציפים הקטן ביותר הדרוש

אילוצים

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
כל זמן בפורמט HHMM הוא זמן תקין: שתי הספרות האחרונות שלו הן לכל היותר 59.
כל הרכבות נוסעות באותו יום. המערכים אינם ממוינים.

דוגמאות

קלט: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
פלט: 3
הסבר: בשעה 15:30 שלוש רכבות עומדות בתחנה: אלה שבין 15:00 ל-16:00, בין 15:20 ל-15:35 ובין 15:30 ל-15:45. אין דקה שבה יש ארבע רכבות, לכן 3 רציפים מספיקים.

קלט: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
פלט: 2
הסבר: הרכבת שמגיעה ב-12:30 פוגשת את זו שיוצאת ב-12:30, ואותו הדבר קורה ב-13:00. בכל אחת מהדקות האלה יש שתי רכבות בתחנה, לכן התשובה היא 2, ולא 1.

קלט: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
פלט: 2
הסבר: הרכבת מ־06:00 עד 22:00 משאירה רציף אחד תפוס כל היום. הרכבות מ־07:00 עד 07:15 ומ־13:00 עד 14:00 לעולם אינן נפגשות, ולכן הן חולקות רציף שני: 2.

שאלת המשך

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

פתרון

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

ספרו את הרכבות בכל הגעה

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

האינטואיציה

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

מספר הרכבות שנמצאות בתחנה גדל רק כשמגיעה רכבת, ולכן הדקה העמוסה ביותר היא דקת הגעה של רכבת כלשהי. עבור כל רכבת i, סופרים את הרכבות j שעבורן arrival[j] ≤ arrival[i] ≤ departure[j]. בשתי ההשוואות משתמשים ב-≤, מפני שרכבת עדיין עומדת ברציף שלה בדקה שבה היא עוזבת.

כל אחת מ-n הרכבות בודקת את כולן, ולכן העבודה היא O(n²): 25 מיליון בדיקות זוגות עבור 5000 רכבות.

אלגוריתם

הגדר את most = 0.
עבור כל רכבת i, ספור את הרכבות j שעבורן מתקיים arrival[j] ≤ arrival[i] ≤ departure[j].
אם המספר הזה גדול מ־most, שמור אותו.
החזר את most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

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

האינטואיציה

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

במקרה של שוויון, ההגעה קודמת, כי הרכבת שעוזבת עדיין תופסת את הרציף באותה דקה. בדוגמה הראשונה, הספירה חוזרת ל־0 אחרי היציאה ב־1100, ואז ההגעות ב־1500, 1520 ו־1530 מתרחשות כולן לפני היציאה ב־1535, כך שהספירה מגיעה ל־3.

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

אלגוריתם

מיינו עותק של arrival ועותק של departure.
הגדירו את platforms, את most, את i ואת j ל־0.
כל עוד i < n: אם arrivals[i] ≤ departures[j], הוסיפו 1 ל־platforms, עדכנו את most והתקדמו עם i.
אחרת, הפחיתו 1 מ־platforms והתקדמו עם j.
החזירו את most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

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

השוואה באמצעות < במקום שבו הכלל הכולל את הגבול דורש ≤. בדוגמה השנייה, כל רכבת שמגיעה תופסת את הרציף של הרכבת שיוצאת באותה דקה, והתשובה יורדת מ־2 ל־1.
חיסור של מספרי HHMM: ‏1300 פחות 1259 הם 41, אף שהזמנים מרוחקים זה מזה בדקה אחת. בטוח להשוות ביניהם, והפתרון משווה בלבד.
מיון הרכבות לפי שעת ההגעה והשוואה של כל אחת מהן רק לרכבת שלפניה. שהייה ארוכה, כמו מ־06:00 עד 22:00 בדוגמה השלישית, חופפת לרכבות שנמצאות הרבה בהמשך הרשימה.
דילוג על רכבות שמגיעות ויוצאות באותה דקה. ארבע רכבות שכל אחת מהן עומדת ברציף מ־10:00 עד 10:00 צריכות ארבעה רציפים.

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

מהי סיבוכיות הזמן של בעיית מספר הרציפים המינימלי?

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

במה שונה בעיית מינימום הרציפים מבעיית חדרי הישיבות II?

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

האם אפשר לפתור את בעיית מספר הרציפים המינימלי בלי למיין?

כן, כי כל שעה מתאימה לשעה קבועה בשעון. מַדֵּד 2401 מונים לפי מספר HHMM, הוסף 1 בכל הגעה והפחת 1 ב-departure + 1. הסכום המצטבר הגדול ביותר הוא התשובה: זמן של O(n + 2400). אינדקסים כמו 1260 עד 1299 אינם שעות בשעון ולא מתרחשת בהם הגעה, ולכן הם לעולם לא קובעים שיא.

def minimumPlatforms(arrival, departure):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

הפלט הצפוי