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]. يمكن إكمال كل المقررات بالضبط عندما لا يحتوي هذا الرسم البياني على دورة. تحسم خوارزمية كان الأمر بالطريقة التي قد يخطط بها طالب: واصل أخذ مقرر تكون جميع متطلباته السابقة قد أُنجزت، ولاحظ ما إذا كنت ستنفد المقررات أم الخيارات أولًا.
احصل على كل دورة مجانية، جولة بعد جولة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
خطّط بالطريقة التي قد يتبعها الطالب. في كل جولة، انظر إلى كل مقرر لم تأخذه بعد. إذا كنت قد أنهيت جميع المتطلبات السابقة له، فخذه. كرر ذلك حتى تمر جولة لا تأخذ فيها أي مقرر. إذا كنت قد أنهيت جميع المقررات بحلول ذلك الوقت، فالإجابة هي صحيح.
لماذا تعني الجولة المتوقفة أن الإجابة خطأ: عندما لا تأخذ أي مقرر في جولة، يكون لكل مقرر متبقٍ متطلب سابق ما زال متبقياً أيضاً. ابدأ بأي مقرر متبقٍ، واستمر في الانتقال إلى أحد متطلباته السابقة التي لم تأخذها. لن تنفد منك الخطوات، وبما أن عدد المقررات محدود، فستعود إلى مقرر سبق أن زرته. هذه دورة، والمقررات التي فيها تنتظر بعضها بعضاً إلى الأبد.
الطريقة صحيحة، لكن في كل جولة يُعاد فحص كل زوج وكل مقرر، وقد لا تأخذ الجولة سوى مقرر واحد. سلسلة من 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 أبدًا، وتكون الإجابة خطأ. - استخدام حالتين بدلًا من ثلاث في البحث بالعمق أولًا. في الشكل الماسي 0 → 1، 0 → 2، 1 → 3، 2 → 3، يُوصَل إلى المقرر 3 مرتين، وهذا يبدو كأنه دورة إذا كنت تتتبع فقط «تمت رؤيته». لا تُغلق الحلقة إلا بعودة سهم إلى المسار الحالي.
- الاستدعاء التكراري في السلاسل الطويلة. يصل عمق سلسلة من 5,000 مقرر إلى 5,000 استدعاء، متجاوزًا الحد الافتراضي في Python البالغ 1,000.
- إرجاع true عندما يفرغ الطابور من دون مقارنة عدد المقررات التي أُخذت مع
numCourses.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة جدولة المقررات؟
O(V + E)، حيث إن V هو عدد المقررات وE هو عدد الأزواج، باستخدام خوارزمية كان أو البحث بالعمق أولًا. يقرأ إنشاء القوائم كل زوج مرة واحدة، ويدخل كل مقرر إلى قائمة الانتظار مرة واحدة على الأكثر، ويُخفّض كل زوج عددًا واحدًا مرة واحدة. وتستهلك القوائم والعدادات مساحة O(V + E).
لماذا يعني وجود مقرر متبقٍ في خوارزمية كان وجودَ دورة؟
لا تبقى دورة دراسية إلا إذا لم يصل عددها إلى 0 مطلقًا، لذا يبقى واحد على الأقل من متطلباتها السابقة أيضًا. تتبّع هذا الانتظار من دورة دراسية إلى أخرى: كل خطوة تصل إلى دورة دراسية أخرى متبقية، وبما أن عدد الدورات الدراسية محدود، فلا بد أن تعود الجولة إلى دورة سبق أن مرّت بها. والجزء الممتد بين الزيارتين يشكّل دورة.
هل ينبغي استخدام BFS أم DFS لجدول المقررات؟
كلاهما يعمل في زمن O(V + E). لا توجد في خوارزمية كان، وهي النسخة المعتمدة على البحث بالعرض أولًا، مشكلة عمق الاستدعاء التعاودي، كما أنها تمنحك ترتيبًا صالحًا للمقررات مجانًا. البحث بالعمق أولًا باستخدام ثلاث حالات سريع بالقدر نفسه، وهو الخيار الطبيعي عندما يتعين عليك أيضًا الإبلاغ عن الدورة، لأن المقررات الموجودة في مكدسه تكوّنها.
ما هو الترتيب الطوبولوجي؟
ترتيب لعُقد رسم بياني موجّه بحيث يشير كل سهم إلى الأمام؛ وهنا، ترتيب للمقررات يأتي فيه كل متطلب سابق قبل المقرر الذي يحتاج إليه. يوجد هذا الترتيب بالضبط عندما لا تحتوي الرسمة البيانية على دورة، والترتيب الذي يأخذ به كاهن المقررات هو أحد هذه الترتيبات. تسأل مسألة Course Schedule عمّا إذا كان يوجد ترتيب طوبولوجي.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def canFinish(numCourses, prerequisites):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
المتوقع
true