Course Schedule
יש numCourses קורסים, שממוספרים מ־0 עד numCourses-1. כל זוג [a, b] ב־prerequisites פירושו שעליך לסיים את הקורס b לפני שתוכל להתחיל את הקורס a. החזר true אם יש סדר שבו תוכל לסיים כל קורס, ו־false אם אין כזה.
פונקציה
- numCoursesinteger
- מספר הקורסים
- prerequisitesinteger-2d-array
- הזוגות [a, b], שכל אחד מהם מציין שהקורס b קודם לקורס a
- מחזירהboolean
- אמת אם ניתן לסיים כל קורס, אחרת שקר
אילוצים
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- לכל זוג
[a, b]מתקיים0 ≤ a, b < numCourses. - אף זוג אינו מופיע פעמיים.
- זוג יכול לציין את אותו קורס פעמיים,
[a, a]. הקורס הזה צריך להיות קודם לעצמו, ולכן אי אפשר לקחת אותו לעולם.
דוגמאות
- קלט
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- פלט
- true
- הסבר
- לקורס 0 אין דרישות קדם, לכן לומדים אותו ראשון. כך מתפנה קורס 1, וקורס 1 מאפשר ללמוד גם את 2 וגם את 3, ולכן הסדר 0, 1, 2, 3 מתאים.
- קלט
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- פלט
- false
- הסבר
- קורס 0 ממתין לקורס 2, קורס 2 ממתין לקורס 1, וקורס 1 ממתין לקורס 0. שלושתם ממתינים זה לזה בלולאה, ולכן אף אחד מהם לא יכול להיות הראשון שתיקח.
+20 בדיקות נסתרות בשליחה
שאלת המשך
אפשר ללמוד כל מספר של קורסים בסמסטר אחד, כל עוד תנאי הקדם של כל קורס הושלמו בסמסטרים קודמים. מהו המספר הקטן ביותר של סמסטרים שבו אפשר להשלים את כל הקורסים?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ציירו כל קורס כנקודה וכל זוג
[a, b]כחץ מ־bאלa. איזו צורה בציור הזה תהפוך את האפשרות להשלים לבלתי אפשרית?לולאה של חצים. כל קורס בלולאה ממתין לקורס אחר באותה לולאה, ולכן אף אחד מהם לא יכול להיות ראשון. השאלה היא האם יש בגרף מעגל.
ספרו לכמה קורסי קדם כל קורס עדיין ממתין. התחילו תור עם הקורסים שהספירה שלהם היא 0, ובכל פעם שמוציאים קורס מהתור, הפחיתו את הספירה של כל קורס שממתין לו. אם פחות מ־
numCoursesקורסים מגיעים אי־פעם לתור, יש מעגל.
פתרון
הפכו את הזוגות לגרף מכוון עם V = numCourses צמתים ו-E = prerequisites.length קשתות, חץ אחד b → a עבור כל זוג [a, b]. אפשר לסיים כל קורס בדיוק כאשר אין בגרף מעגל. האלגוריתם של Kahn מכריע זאת כפי שסטודנט היה מתכנן: ממשיכים ללמוד קורס שכל דרישות הקדם שלו הושלמו, ובודקים אם נגמרים הקורסים או האפשרויות קודם.
קח כל קורס בחינם, סיבוב אחר סיבוב
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
תכננו כפי שתלמיד היה מתכנן. בכל סבב, בדקו כל קורס שעדיין לא לקחתם. אם כל קורסי הקדם שלו נלקחו, קחו אותו. חזרו על הפעולה עד שסבב לא לוקח שום קורס. אם עד אז נלקחו כל הקורסים, התשובה היא אמת.
למה סבב שנתקע פירושו שקר: כשסבב לא לוקח שום קורס, לכל קורס שנותר יש קורס קדם שגם הוא נותר. התחילו בכל קורס שנותר והמשיכו לעבור לאחד מקורסי הקדם שלו שעדיין לא נלקחו. לא ייגמרו לכם הצעדים, ויש רק מספר סופי של קורסים, לכן תחזרו לקורס שכבר ביקרתם בו. זהו מחזור, והקורסים שבו מחכים זה לזה לנצח.
השיטה נכונה, אבל בכל סבב קוראים מחדש כל זוג וכל קורס, וסבב יכול לקחת קורס אחד בלבד. שרשרת של 5,001 קורסים, שכל אחד מהם דורש את הקורס שלפניו, מצריכה יותר מ־5,000 סבבים; מתוך 100,000 קורסים, מדובר בכ־5 × 10^8 בדיקות, שכמעט כולן נעשות בקורסים שמצבם לא השתנה.
אלגוריתם
- סמן כל קורס כלא נלקח.
- סמן קורס כחסום אם זוג כלשהו נותן לו קדם־דרישה שלא נלקחה.
- קח כל קורס שלא נלקח ולא נחסם.
- אם בסבב לא נלקח דבר, עצור; אחרת חזור לשלב 2.
- החזר true אם כל הקורסים נלקחו.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesחיפוש לעומק תחילה עם שלושה מצבים
האינטואיציה
מעגל הוא מסלול שחוזר לנקודת ההתחלה שלו. חיפוש לעומק מוצא מעגל באמצעות מעקב אחר הקורסים שנמצאים כרגע במסלול שבו הוא מתקדם. תן לכל קורס אחד משלושה מצבים: לא בוקר, במסלול הנוכחי והסתיים.
התקדם מקורס לאורך החצים שלו אל הקורסים שממתינים לו. סמן קורס כ״במסלול״ כשאתה נכנס אליו, וכ״הסתיים״ כשכל החצים היוצאים ממנו נבדקו ואתה חוזר ממנו. חץ אל קורס שנמצא במסלול פירושו שהלכת במעגל: החזר false. חץ אל קורס שהסתיים בטוח, כי כל מה שניתן להגיע אליו ממנו נבדק ונמצא שאין בו מעגל, ולכן אפשר לדלג עליו. נכנסים לכל קורס פעם אחת ועוקבים אחר כל חץ פעם אחת.
שני מצבים אינם מספיקים. ביהלום 0 → 1, 0 → 2, 1 → 3, 2 → 3 החיפוש מגיע לקורס 3 פעם שנייה דרך 2, אבל עד אז 3 כבר הסתיים ואינו במסלול, ואין מעגל. רק חץ שחוזר אל המסלול הנוכחי סוגר מעגל.
כתוב את החיפוש בעזרת מחסנית משלך, ושמור לכל קורס את המיקום של החץ הבא שעדיין לא נבדק. הגרסה הרקורסיבית קצרה יותר, אבל שרשרת של 5,000 קורסים תגיע לעומק של 5,000 קריאות.
אלגוריתם
- בנו, עבור כל קורס, את רשימת הקורסים שממתינים לו.
- עבור כל קורס שלא בוקר, סמנו אותו במסלול ודחפו אותו למחסנית.
- בדקו את ראש המחסנית. אם לא נותר בו חץ, סמנו אותו כהושלם והוציאו אותו מהמחסנית; אחרת, עקבו אחר החץ הבא שלו.
- אם החץ מוביל לקורס שנמצא במסלול, החזירו false. אם הוא מוביל לקורס שלא בוקר, סמנו את הקורס הזה במסלול ודחפו אותו למחסנית.
- כאשר כל הקורסים הושלמו, החזירו true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return Trueהאלגוריתם של קאהן
האינטואיציה
הסבבים בגישה הראשונה מבזבזים זמן בבדיקה חוזרת של קורסים שלא השתנו. קורס מתפנה ברגע אחד בלבד: כשנלקחת דרישת הקדם האחרונה שלו. לכן, ספור עבור כל קורס כמה דרישות קדם עדיין ממתינות לו — דרגת הכניסה שלו. כשאתה לוקח קורס, הפחת את הספירה של כל קורס שממתין לו. ספירה שיורדת ל־0 פירושה שהקורס הזה פנוי עכשיו, ולכן מכניסים אותו לתור.
התחל את התור עם כל הקורסים שהספירה שלהם היא 0 מלכתחילה, ואז הוצא קורסים מהתור עד שהוא מתרוקן. בדוגמה הראשונה הספירות מתחילות ב־0, 1, 1, 1 עבור הקורסים 0 עד 3. הוצאת 0 מורידה את הספירה של קורס 1 ל־0; הוצאת 1 מורידה את הספירות של הקורסים 2 ו־3 ל־0; כל ארבעת הקורסים נלקחים, ולכן התשובה היא true. כל קורס נכנס לתור לכל היותר פעם אחת וכל זוג מוריד ספירה פעם אחת, ולכן העבודה היא O(V + E).
למה קורס שנותר פירושו שיש מעגל: אם התור מתרוקן כשקורס a עדיין לא נלקח, הספירה שלו גדולה מ־0, ולכן גם אחת מדרישות הקדם שלו, b, לא נלקחה. הדבר נכון גם לגבי b, וכן הלאה. מסלול מקורס לדרישת קדם שלא נלקחה לעולם לא נעצר, ולכן הוא חוזר לקורס שכבר ביקר בו — כלומר יש מעגל. בדוגמה השנייה אף ספירה לא מתחילה ב־0, התור מתחיל ריק, ואף אחד משלושת הקורסים לא נלקח.
גם הכיוון השני נכון: קורס שנמצא במעגל ממתין לקורס אחר מאותו מעגל, ולכן הספירה שלו לא יכולה להגיע ל־0 לפני שהקורס האחר נלקח, ואף אחד מהם לא יכול להיות הראשון. לכן ״כל הקורסים נלקחים״ ו״אין מעגל״ הם אותו הדבר. כבונוס, סדר הקורסים שיצאו מהתור הוא לוח זמנים תקף.
אלגוריתם
- עבור כל זוג [a, b], הוסף את a לרשימת הקורסים שממתינים ל-b, והוסף 1 לדרגת הכניסה של a.
- הכנס לתור כל קורס שדרגת הכניסה שלו היא 0.
- הוצא קורס מהתור וספור אותו. הפחת את דרגת הכניסה של כל קורס שממתין לו, והוסף לתור כל קורס שדרגת הכניסה שלו מגיעה ל-0.
- כשהתור ריק, החזר האם הספירה שווה ל-
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
מלכודות ומקרי קצה
רוב הבאגים נובעים מהכיוון של זוג, מבדיקת מעגלים מחמירה מדי או מקורסים שאינם מופיעים באף זוג.
- בלבול בכיוון.
[a, b]פירושו ש־b מגיע קודם, ולכן החץ יוצא מ־b ומצביע אל a והדרגה הפנימית של a עולה. בניית הרשימות בכיוון אחד וספירת הדרגות הפנימיות בכיוון השני משבשת את האלגוריתם. - שוכחים קורסים שאינם מופיעים באף זוג. עם
numCourses = 5והזוג היחיד[4, 3], גם הקורסים 0, 1 ו־2 עדיין נספרים. מתחילים את התור עם כל קורס שהדרגה הפנימית שלו היא 0, ולא רק עם אלה שראיתם בזוג. - קורס שהוא דרישת קדם של עצמו,
[2, 2]. זהו מעגל באורך אחד: הדרגה הפנימית שלו לעולם אינה מגיעה ל־0 והתשובה היא false. - שני מצבים במקום שלושה בחיפוש לעומק. במבנה היהלום 0 → 1, 0 → 2, 1 → 3, 2 → 3, מגיעים לקורס 3 פעמיים, וזה נראה כמו מעגל אם עוקבים רק אחרי "seen". רק חץ שחוזר אל הנתיב הנוכחי סוגר לולאה.
- רקורסיה בשרשראות ארוכות. שרשרת של 5,000 קורסים מגיעה לעומק של 5,000 קריאות, מעבר למגבלת ברירת המחדל של Python, שהיא 1,000.
- מחזירים true כשהתור מתרוקן בלי להשוות את מספר הקורסים שנלמדו ל־
numCourses.
שאלות נפוצות4
מהי סיבוכיות הזמן של בעיית לוח הזמנים של הקורסים?
O(V + E), כאשר V הוא מספר הקורסים ו-E הוא מספר הזוגות, באמצעות האלגוריתם של קאהן או חיפוש לעומק. בניית הרשימות קוראת כל זוג פעם אחת, כל קורס נכנס לתור לכל היותר פעם אחת, וכל זוג מפחית ספירה אחת פעם אחת. הרשימות והספירות תופסות O(V + E) מקום.
למה קורס שנותר באלגוריתם של קאן מעיד על קיומו של מעגל?
קורס נותר רק אם הספירה שלו מעולם לא הגיעה ל־0, ולכן גם לפחות אחד מקורסי הקדם שלו נותר. עקבו אחר הקשר הזה מקורס לקורס: כל צעד מוביל לקורס אחר שנותר, ומכיוון שיש מספר סופי של קורסים, המסלול חייב לחזור לקורס שכבר עבר בו. הקטע שבין שני הביקורים הוא מעגל.
האם כדאי להשתמש ב-BFS או ב-DFS לתזמון קורסים?
שתיהן פועלות בזמן O(V + E). לאלגוריתם של Kahn, הגרסה המבוססת על חיפוש לרוחב, אין עומק רקורסיה שצריך לדאוג לו, והוא מספק לך סדר תקף של קורסים בחינם. חיפוש לעומק עם שלושה מצבים מהיר באותה מידה והוא הבחירה הטבעית כשצריך גם לדווח על המעגל, כי הקורסים שבמחסנית שלו מרכיבים אותו.
מהו מיון טופולוגי?
סדר של הצמתים בגרף מכוון, שבו כל חץ מצביע קדימה; כאן, סדר של קורסים שבו כל קדם־דרישה מופיעה לפני הקורס שזקוק לה. סדר כזה קיים בדיוק כאשר אין בגרף מעגל, והסדר שבו האלגוריתם של Kahn לוקח קורסים הוא סדר כזה. Course Schedule שואל אם קיים סדר טופולוגי.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def canFinish(numCourses, prerequisites):
# כתבו כאן את הקודמקרה 1
מקרה 2
קלט
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
צפוי
true