Meeting Rooms
מקבלים רשימה של פגישות כשני מערכים: פגישה i מתקיימת מ־starts[i] עד ends[i]. אדם אחד רוצה להשתתף בכולן, ולכן אין אפשרות ששתי פגישות יחפפו. פגישה יכולה להתחיל בדיוק ברגע שפגישה אחרת מסתיימת. החזירו true אם האדם יכול להשתתף בכל הפגישות, ו־false אחרת.
פונקציה
- startsinteger-array
- שעת ההתחלה של כל פגישה
- endsinteger-array
- שעת הסיום של כל פגישה, באותו אינדקס כמו שעת ההתחלה שלה
- מחזירהboolean
- true אם אין חפיפה בין פגישות, אחרת false
אילוצים
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- הפגישות אינן ממוינות. ייתכן ששתי פגישות יהיו זהות.
דוגמאות
- קלט
- starts = [9, 13, 10]ends = [10, 15, 12]
- פלט
- true
- הסבר
- לפי סדר הזמנים, הפגישות מתקיימות מ־9 עד 10, מ־10 עד 12 ומ־13 עד 15. הפגישה השנייה מתחילה ברגע שהראשונה מסתיימת, וזה מותר, לכן התשובה היא
true.
- קלט
- starts = [1, 4, 7]ends = [5, 6, 8]
- פלט
- false
- הסבר
- הפגישה מ־1 עד 5 עדיין מתקיימת בשעה 4, כאשר הפגישה מ־4 עד 6 מתחילה, ולכן התשובה היא
false.
+15 בדיקות נסתרות בשליחה
שאלת המשך
אם פגישות מוזמנות אחת בכל פעם, איך תבדקו כל הזמנה חדשה מול לוח הזמנים ב־O(log n), בלי למיין הכול מחדש?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
שתי פגישות שמתנגשות חייבות לחפוף בחלק מהזמן. באיזה סדר אפשר לרשום את הפגישות כך שתופיע התנגשות בין פגישות סמוכות?
סדרו את הפגישות לפי שעת ההתחלה. כך פגישה יכולה להתנגש רק עם הפגישה שמיד לפניה: אם היא מתחילה אחרי שהפגישה ההיא מסתיימת, היא מתחילה גם אחרי שכל הפגישות הקודמות מסתיימות.
מיין את הפגישות לפי שעת ההתחלה, תוך שמירה על ההתאמה בין כל שעת התחלה לשעת הסיום שלה. עבור על הרשימה הממוינת והשווה כל שעת התחלה לשעת הסיום של הפגישה שלפניה. שעת התחלה מוקדמת יותר פירושה התנגשות; שעת התחלה ששווה לשעת הסיום הזאת היא בסדר.
פתרון
בדיקת כל זוג של פגישות מאפשרת למצוא כל התנגשות, אך העלות שלה היא O(n²). מיון לפי שעת ההתחלה משנה את השאלה: כעת פגישה יכולה להתנגש רק עם הפגישה שלצידה בסדר הממויין, ולכן מספיקה השוואה אחת לכל פגישה.
השוו כל זוג
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
שתי פגישות מתנגשות כאשר כל אחת מהן מתחילה לפני שהשנייה מסתיימת. עבור פגישות בין 1 ל־5 ובין 4 ל־6: 1 נמצא לפני 6 ו־4 נמצא לפני 5, ולכן הן מתנגשות. עבור פגישות בין 9 ל־10 ובין 10 ל־12: 10 לא נמצא לפני 10, ולכן הן רק נוגעות זו בזו.
שימוש ב־< strict בשני הצדדים מאפשר לפגישה להתחיל בדיוק כשפגישה אחרת מסתיימת. הריצו את הבדיקה על כל זוג והחזירו false בהתנגשות הראשונה.
הבעיה היא מספר הזוגות. כשיש n = 5000 פגישות יש כ־12.5 מיליון זוגות, ולוח זמנים ללא התנגשויות מחייב לבדוק את כולם, וזה איטי מדי עבור הבדיקות הגדולות ביותר.
אלגוריתם
- עבור כל אינדקס
i, וכל אינדקסjשמופיע אחריו: - אם
starts[i] < ends[j]וגםstarts[j] < ends[i], שתי הפגישות חופפות: החזרfalse. - אם אין זוגות חופפים, החזר
true.
def canAttendMeetings(starts, ends):
n = len(starts)
for i in range(n):
for j in range(i + 1, n):
# two meetings clash when each one starts before the other ends
if starts[i] < ends[j] and starts[j] < ends[i]:
return False
return Trueמיין לפי התחלה ובדוק את השכנים
האינטואיציה
מיין את הפגישות לפי שעת ההתחלה, תוך שמירה על הקשר בין כל שעת התחלה לשעת הסיום שלה. כעת התבונן בכל פגישה ובזו שמיד לפניה. אם הפגישה המוקדמת יותר מסתיימת אחרי שהמאוחרת יותר מתחילה, הן מתנגשות. אם לא, הפגישה המאוחרת יותר מתחילה בזמן הסיום של המוקדמת יותר או אחריו.
למה צריך לבדוק רק את הפגישה השכנה? אם כל פגישה עד כה מתחילה בזמן הסיום של זו שלפניה או אחריו, הפגישות עד כה אף פעם לא חופפות, והפגישה שמיד לפני הנוכחית היא זו שמסתיימת הכי מאוחר. פגישה חדשה שמתחילה בזמן הסיום שלה או אחריו מתחילה בזמן הסיום של כולן או אחריו.
בדוגמה הראשונה הפגישות הממוינות הן מ־9 עד 10, מ־10 עד 12, ומ־13 עד 15. שעת ההתחלה 10 אינה לפני שעת הסיום 10, ושעת ההתחלה 13 אינה לפני שעת הסיום 12, ולכן אין התנגשות. שעות התחלה זהות תמיד גורמות להתנגשות, מכיוון שכל פגישה נמשכת לפחות יחידת זמן אחת, וגם הבדיקה מזהה אותן.
המיון עולה O(n log n) והמעבר עולה O(n). העותק שבו זמני ההתחלה והסיום משויכים זה לזה תופס O(n) מקום.
אלגוריתם
- התאם כל שעת התחלה לשעת הסיום שלה.
- מיין את הזוגות לפי שעת ההתחלה.
- עבור כל פגישה אחרי הראשונה, השווה את שעת ההתחלה שלה לשעת הסיום של הפגישה שלפניה.
- אם שעת ההתחלה קטנה יותר, החזר
false. - אחרי הלולאה, החזר
true.
def canAttendMeetings(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
for i in range(1, len(meetings)):
# a meeting must not start before the one right before it ends
if meetings[i][0] < meetings[i - 1][1]:
return False
return True
מלכודות ומקרי קצה
הבאגים הנפוצים קשורים לשאלה אילו קצוות משווים ואיך מתייחסים לפגישות שנוגעות זו בזו.
- ממיינים את
startsומשאירים אתendsבסדר המקורי של הקלט. כל שעת סיום צריכה להישאר לצד שעת ההתחלה שלה, אחרת משווים שעת התחלה לשעת סיום של פגישה אחרת. - משתמשים ב־
≤במקום ב־<. פגישות מ־9 עד 10 ומ־10 עד 12 נוגעות זו בזו אך אינן חופפות, והתשובה עבורן היאtrue. - בודקים רק שכל פגישה מסתיימת לפני שהבאה אחריה מתחילה, לפי סדר הקלט. הקלט אינו ממוין, ולכן אין להסיק דבר מפגישות סמוכות בקלט.
- כותבים את בדיקת הזוגות עם תנאי אחד, כמו
starts[j] < ends[i]. התנאי הזה תקף רק כאשר פגישהjמתחילה מאוחר יותר; עבור פגישות מ־5 עד 6 ומ־0 עד 1, בסדר הזה,0 < 6מדווח על התנגשות שאינה קיימת.
שאלות נפוצות4
מהי סיבוכיות הזמן של Meeting Rooms?
מיון הפגישות לפי שעת ההתחלה עולה O(n log n), והמעבר שמשווה בין שכנים עולה O(n), ולכן העלות הכוללת היא O(n log n). השוואה של כל זוג עולה במקום זאת O(n²).
למה מספיק להשוות כל פגישה לזו שלפניה?
לאחר מיון לפי שעת ההתחלה, אם לא נמצאה עד כה התנגשות, הפגישות עד כה יוצרות שרשרת שבה כל פגישה מתחילה בזמן סיום הפגישה הקודמת או אחריו. הפגישה האחרונה בשרשרת מסתיימת בזמן המאוחר ביותר. פגישה חדשה שמתחילה בזמן סיומה או אחריו אינה יכולה לחפוף לאף אחת מהפגישות הקודמות.
האם פגישות שנוגעות זו בזו נחשבות לחופפות?
לא במקרה הזה: פגישה יכולה להתחיל בדיוק ברגע שפגישה אחרת מסתיימת. לכן הבדיקה היא start < previous end מחמירה. אם פגישות צמודות היו אסורות, הבדיקה הייתה הופכת ל־start ≤ previous end.
איך מוצאים את המספר המינימלי של חדרי ישיבות?
מיינו את זמני ההתחלה ואת זמני הסיום בשתי רשימות נפרדות, ואז עברו על שתיהן: כל שעת התחלה פותחת חדר, וכל שעת סיום שמגיעה לפני שעת ההתחלה הבאה או במקביל לה מפנה חדר. התשובה היא המספר המרבי של חדרים שפתוחים בו־זמנית. התשובה לשאלת כן או לא כאן זהה לשאלה אם חדר אחד מספיק.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def canAttendMeetings(starts, ends):
# כתבו כאן קודמקרה 1
מקרה 2
קלט
starts = [9, 13, 10] ends = [10, 15, 12]
צפוי
true