Meeting Rooms II

Q: ما هو التعقيد الزمني لمسألة Meeting Rooms II؟

يعمل كلا الحلين السريعين بزمن O(n log n) . يرتب إصدار الكومة الاجتماعات، وينفذ عملية كومة واحدة بزمن O(log n) لكل اجتماع؛ أما الإصدار ذو القائمتين فينفذ عمليتي فرز واجتيازًا واحدًا بزمن O(n) . يستخدم كلاهما مساحة إضافية قدرها O(n) . ويستغرق عدّ الاجتماعات الجارية عند كل بداية زمنًا قدره O(n²) .

متوسطالفترات الكومة الترتيب

+10

لديك قائمة بالاجتماعات ممثلة بمصفوفتين: يمتد الاجتماع i من starts[i] إلى ends[i]. تستوعب الغرفة اجتماعًا واحدًا في كل مرة، ويمكن أن يبدأ اجتماع في غرفة في اللحظة نفسها التي ينتهي فيها اجتماع آخر فيها.

اكتب دالة باسم minMeetingRooms تُرجع أصغر عدد من الغرف التي يمكنها استيعاب جميع الاجتماعات.

الدالة

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: وقت بدء كل اجتماع
endsinteger-array: وقت انتهاء كل اجتماع، عند الفهرس نفسه الذي يبدأ فيه
تُرجعinteger: أقل عدد من الغرف التي يمكنها استيعاب جميع الاجتماعات

القيود

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
الاجتماعات غير مرتبة. قد يكون اجتماعان متطابقين.

أمثلة

المدخلات: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
المخرجات: 3
الشرح: في الوقت 4، تكون الاجتماعات من 1 إلى 5، ومن 2 إلى 6، ومن 4 إلى 8 جاريةً جميعها، لذا تحتاج إلى 3 غرف على الأقل. ثلاث غرف تكفي: فالاجتماع من 7 إلى 9 يشغل الغرفة التي تصبح شاغرة عند 5.

المدخلات: starts = [0, 2, 3]ends = [10, 3, 5]
المخرجات: 2
الشرح: يشغل الاجتماع من 0 إلى 10 غرفةً واحدة طوال الوقت. يحتاج الاجتماع من 2 إلى 3 إلى غرفة ثانية، ويشغل الاجتماع من 3 إلى 5 الغرفة نفسها عندما تصبح شاغرة، لذا تكفي 2 غرف.

+17 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك أيضًا تحديد الغرفة التي يُعقد فيها كل اجتماع، باستخدام عدد من الغرف لا يتجاوز الإجابة؟

الحل

عدد الغرف التي تحتاج إليها هو أكبر عدد من الاجتماعات التي تُعقد في الوقت نفسه. ويؤدي عدّ الاجتماعات الجارية عند كل وقت بدء إلى إيجاد ذلك في O(n²). يحوّل الفرز السؤال إلى مرور واحد على اليوم: إذ تمنحك كومة صغرى لأوقات إخلاء الغرف، أو قائمتان مرتبتان لأوقات البدء والانتهاء، الإجابة في O(n log n).

عدّ الاجتماعات الجارية عند كل وقت بدء

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

في أي لحظة، يحتاج كل اجتماع جارٍ إلى غرفة خاصة به. لذلك تحتاج إلى عدد من الغرف لا يقل عن أكبر عدد من الاجتماعات الجارية في الوقت نفسه. وهذا العدد كافٍ أيضًا: وزّع الغرف بحسب أوقات البدء، ولن تُفتح غرفة جديدة إلا عندما تكون جميع الغرف مشغولة، ما يعني أن هذا العدد من الاجتماعات جارٍ في تلك اللحظة.

لا يزداد عدد الاجتماعات الجارية إلا عند بدء اجتماع، لذا تكون اللحظة الأكثر ازدحامًا هي لحظة بدء أحد الاجتماعات. لكل اجتماع i، احسب الاجتماعات j التي تحقق starts[j] ≤ starts[i] < ends[j]: أي الاجتماعات التي بدأت ولم تنتهِ بعد. لا يُحتسب الاجتماع الذي ينتهي تمامًا عند starts[i]، لأن غرفته تصبح متاحة مجددًا في تلك اللحظة.

في المثال الأول، عند الوقت 4، تكون الاجتماعات من 1 إلى 5، ومن 2 إلى 6، ومن 4 إلى 8 جارية: 3. عند الوقت 7، لا يكون جاريًا سوى الاجتماعَين من 4 إلى 8 ومن 7 إلى 9: 2. أكبر عدد هو 3.

يفحص كل اجتماع من الاجتماعات n الاجتماعاتَ كلها. عندما يكون n = 5000، فهذا يعني 25 مليون عملية تحقق: جزءًا من الثانية في C، وعدة ثوانٍ في Python أو R، وأربعة أضعاف ذلك في كل مرة يتضاعف فيها n.

الخوارزمية

لكل اجتماع i، عيّن running إلى 0.
لكل اجتماع j، أضف 1 إلى running عندما يكون starts[j] ≤ starts[i] < ends[j].
احتفظ بأكبر قيمة لـ running رأيتها.
أعِد تلك القيمة الأكبر.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

كومة صغرى للأوقات التي تصبح فيها الغرف شاغرة

الفكرة

عيّن الغرف بالطريقة التي يتبعها موظف الاستقبال. خذ الاجتماعات بترتيب وقت البدء. لكل اجتماع، انظر إلى الغرفة التي ستصبح متاحة أولًا. إذا كانت متاحة عند بدء الاجتماع، يُعقد الاجتماع فيها. وإذا لم تكن كذلك، فهذا يعني أن جميع الغرف لا تزال مشغولة، لذا افتح غرفة جديدة.

التحقق من تلك الغرفة وحدها آمن. فإذا كانت الغرفة التي ستصبح متاحة أولًا لا تزال مشغولة، فكل الغرف مشغولة. وإذا كانت متاحة، فأي غرفة متاحة تصلح مثل غيرها: فالاجتماعات المتبقية تبدأ في هذا الوقت أو بعده، لذا تظل كل غرفة متاحة الآن متاحة لها جميعًا.

أنت بحاجة إلى أقرب وقت تصبح فيه إحدى الغرف متاحة، وهذا الوقت يتغير بعد كل اجتماع. تحتفظ الكومة الصغرى بوقت انتهاء واحد لكل غرفة، وتُعطيك أصغر وقت. عند إعادة استخدام غرفة، يستبدل وقت انتهائها بوقت انتهاء الاجتماع الجديد؛ وعند فتح غرفة، يُضاف وقت انتهاء جديد إلى الكومة. في المثال الأول، بعد الترتيب حسب وقت البدء: الاجتماع من 1 إلى 5 يعطي [5]، والاجتماع من 2 إلى 6 يعطي [5, 6]، والاجتماع من 4 إلى 8 يعطي [5, 6, 8]، والاجتماع من 7 إلى 9 يجد أن 5 يسبق 7 أو يساويه، فيستبدله، لتصبح الكومة [6, 8, 9]. ثلاث غرف.

تستغرق عملية الترتيب O(n log n)، وينفّذ كل اجتماع عملية واحدة على الكومة بتعقيد O(log n). توفر لك heapq في Python، وPriorityQueue في Java، وpriority_queue مع greater في C++، وBinaryHeap مع Reverse في Rust، وcontainer/heap في Go، وSplMinHeap في PHP الكومة. أما في اللغات الأخرى، فتحتفظ بها في مصفوفة: يكون الأب للفهرس i عند (i-1)/2، وتتحرك القيمة إلى الأعلى ما دامت أصغر من أبيها.

الخوارزمية

رتّب الاجتماعات حسب وقت البدء، مع إبقاء كل وقت بدء مرتبطًا بوقت انتهائه.
لكل اجتماع، إذا لم تكن الكومة فارغة وكان أصغر وقت انتهاء فيها يساوي وقت بدء الاجتماع أو يسبقه، فاستبدل وقت الانتهاء هذا بوقت انتهاء الاجتماع.
وإلا، أضف وقت انتهاء الاجتماع إلى الكومة: تُفتح غرفة جديدة.
أعِد حجم الكومة، إذ يقابل كل إدخال فيها غرفةً واحدة.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

رتّب أوقات البدء والانتهاء كلًّا على حدة

الفكرة

تتذكّر الكومة وقت انتهاء كل اجتماع والغرفة التي يخصّها، لكن الإجابة ليست سوى عدد. عندما يبدأ اجتماع، المهم فقط هو ما إذا كان اجتماع ما قد انتهى بحلول ذلك الوقت وأصبحت غرفة متاحة؛ ولا يهم أيّ اجتماع كان. لذا رتّب أوقات البدء وأوقات الانتهاء في قائمتين منفصلتين، ومرّ على أوقات البدء، مستخدمًا مؤشرًا ended ضمن أوقات الانتهاء.

لكل وقت بدء بالترتيب: إذا كان مساويًا أو لاحقًا لـ endTimes[ended]، فهذا يعني أن اجتماعًا قد انتهى بحلول ذلك الوقت. تُخصّص غرفته للاجتماع الجديد، ويتقدّم ended. وإلا، فكل الغرف المستخدمة لا تزال مشغولة، ويزداد rooms بمقدار واحد. يستهلك كل وقت بدء وقت انتهاء واحدًا على الأكثر، بالطريقة نفسها التي تستبدل بها غرفة معاد استخدامها في الكومة وقت انتهاء قديمًا بوقت انتهاء جديد.

في المثال الأول، أوقات البدء هي 1 و2 و4 و7، وأوقات الانتهاء هي 5 و6 و8 و9. تأتي أوقات البدء 1 و2 و4 كلها قبل وقت الانتهاء 5، لذا يرتفع rooms إلى 3. وقت البدء 7 يساوي 5 أو يأتي بعده، لذا يعيد استخدام تلك الغرفة ويتقدّم ended إلى وقت الانتهاء 6. الإجابة هي 3. الرمز ≥ هو ما يسمح للاجتماعات المتلامسة بمشاركة غرفة: في المثال الثاني، يتوافق وقت البدء 12 مع وقت الانتهاء 12 ويعيد استخدام الغرفة.

لا يتجاوز العدد أبدًا الذروة الفعلية: عندما يزداد rooms، يكون وقت الانتهاء التالي لا يزال في المستقبل، لذا تكون الاجتماعات rooms كلها جارية في تلك اللحظة. ويصل العدد أيضًا إلى الذروة، لأن وقت البدء لا يتخطى فتح غرفة إلا إذا كان هناك وقت انتهاء فعلي يساويه أو يسبقه، وقد أتاح غرفة. يستغرق الفرز مرتين O(n log n)، والمرور O(n)، وتتطلب النسخ المرتبة مساحة O(n).

الخوارزمية

رتّب نسخة من أوقات البدء ونسخة من أوقات الانتهاء.
عيّن rooms وended إلى 0.
لكل وقت بدء بالترتيب، إذا كان عند وقت endTimes[ended] أو بعده، فأضف 1 إلى ended: يأخذ الاجتماع غرفةً أُخليت.
وإلا فأضف 1 إلى rooms.
أعِد rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

أخطاء شائعة وحالات حدّية

تحدث معظم الأخطاء في المقارنة عند لحظة التلامس أو في تحديد الغرفة التي يجري التحقق منها.

التحقق من start > end بدلًا من start ≥ end. عندها لا يمكن لاجتماع استخدام غرفة في اللحظة التي تصبح فيها شاغرة، فتحتاج الاجتماعات من 10 إلى 12، ومن 12 إلى 14، ومن 14 إلى 16 إلى غرفتين بدلًا من غرفة واحدة.
التحقق من آخر غرفة فتحتها بدلًا من الغرفة التي ستصبح شاغرة أولًا. في حالة الاجتماعات من 1 إلى 3، ومن 2 إلى 10، ومن 4 إلى 6، تظل آخر غرفة فُتحت مشغولة حتى الساعة 10، لذا تفتح غرفة ثالثة بينما ظلت الغرفة الأولى شاغرة منذ الساعة 3.
أخذ أكبر عدد من الاجتماعات التي تتداخل مع اجتماع واحد، ثم إضافة 1. يتداخل الاجتماع من 0 إلى 10 مع الاجتماعين من 2 إلى 3 ومن 3 إلى 5، لكن هذين الاجتماعين لا يتداخل أحدهما مع الآخر، لذا تكفي غرفتان، لا 3.
الخلط بين النهجين اللذين يعتمدان على الفرز. تحتاج الكومة إلى إقران كل وقت انتهاء بوقت البدء الخاص به قبل الفرز حسب وقت البدء؛ أما نهج القائمتين فيفرز أوقات البدء وأوقات الانتهاء كلًّا على حدة عمدًا.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة Meeting Rooms II؟

يعمل كلا الحلين السريعين بزمن O(n log n). يرتب إصدار الكومة الاجتماعات، وينفذ عملية كومة واحدة بزمن O(log n) لكل اجتماع؛ أما الإصدار ذو القائمتين فينفذ عمليتي فرز واجتيازًا واحدًا بزمن O(n). يستخدم كلاهما مساحة إضافية قدرها O(n). ويستغرق عدّ الاجتماعات الجارية عند كل بداية زمنًا قدره O(n²).

لماذا يحلّ الكومة الصغرى مسألة قاعات الاجتماعات II؟

عند عقد الاجتماعات بترتيب أوقات البدء، الغرفة الوحيدة التي تستحق التحقق منها هي التي تصبح متاحة أولًا. تمنحك كومة صغرى لأوقات الانتهاء هذه الغرفة في O(1)، وتُحدَّث في O(log n). لا تكبر الكومة إلا عندما تكون كل الغرف مشغولة، لذا فإن حجمها النهائي هو أقل عدد من الغرف اللازمة.

هل يمكن حل مسألة قاعات الاجتماعات II دون استخدام كومة؟

نعم. رتّب أوقات البدء وأوقات الانتهاء في قائمتين منفصلتين، ثم مرّ على أوقات البدء باستخدام مؤشر يشير إلى أوقات الانتهاء. يعيد وقت البدء الذي يساوي وقت الانتهاء التالي غير المستخدم أو يتجاوزه استخدام غرفة؛ أما أي وقت بدء آخر فيتطلب فتح غرفة جديدة. تنجح الفكرة نفسها باستخدام خط المسح: حوّل كل اجتماع إلى حدث +1 عند وقت بدئه وحدث -1 عند وقت انتهائه، وعالج أوقات الانتهاء قبل أوقات البدء إذا تساوت الأوقات، وتتبّع أكبر مجموع تراكمي.

هل الإجابة هي نفسها أكبر عدد من الاجتماعات التي تتداخل في وقت واحد؟

نعم. تحتاج الاجتماعات التي تُعقد في الوقت نفسه إلى غرف مختلفة، لذا تحتاج إلى هذا العدد على الأقل. إن تخصيص أي غرفة شاغرة لكل اجتماع، بترتيب وقت البدء، لا يتطلب أبدًا عددًا أكبر من الغرف؛ لذا فإن أكبر عدد من الاجتماعات المتزامنة هو الإجابة بالضبط.

Python

def minMeetingRooms(starts, ends):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

المتوقع

Meeting Rooms II

الدالة

القيود

أمثلة

تلميحات

الحل

عدّ الاجتماعات الجارية عند كل وقت بدء

كومة صغرى للأوقات التي تصبح فيها الغرف شاغرة

رتّب أوقات البدء والانتهاء كلًّا على حدة

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة