Meeting Rooms
لديك قائمة بالاجتماعات على شكل مصفوفتين: يمتد الاجتماع i من starts[i] إلى ends[i]. يريد شخص حضورها جميعًا، لذا يجب ألا يتداخل أي اجتماعين. يمكن أن يبدأ اجتماع في اللحظة نفسها التي ينتهي فيها اجتماع آخر. أعد true إذا كان بإمكان الشخص حضور كل اجتماع، وإلا فأعد false.
الدالة
- startsinteger-array
- وقت بدء كل اجتماع
- endsinteger-array
- وقت انتهاء كل اجتماع، في الفهرس نفسه الذي يوجد فيه وقت بدايته
- تُرجعboolean
- صحيح إذا لم يتداخل أي اجتماعين، وخطأ خلاف ذلك
القيود
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، لذا فهما يتلامسان فقط.
استخدام < الصارمة على الجانبين هو ما يسمح ببدء اجتماع في اللحظة نفسها التي ينتهي فيها اجتماع آخر. نفّذ الاختبار على كل زوج وأعِد 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
ما هو التعقيد الزمني لمسألة غرف الاجتماعات؟
ترتيب الاجتماعات حسب وقت البدء تكلفته 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