Minimum Platforms

Q: ما هو التعقيد الزمني لمسألة الحد الأدنى من الأرصفة؟

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

Q: ما الفرق بين مشكلة الحد الأدنى من المنصات ومشكلة قاعات الاجتماعات II؟

كلاهما يطلبان أكبر عدد من الفترات التي تتداخل في لحظة واحدة. هنا يشغل القطار رصيفه حتى الدقيقة التي يغادر فيها؛ أما في «قاعات الاجتماعات II»، فتكون القاعة متاحة لحظة انتهاء اجتماعها. في المسح، يتطلب ذلك مقارنة واحدة: عند التعادل، تعالج الوصول أولًا هنا، والاجتماع المنتهي أولًا هناك.

Q: هل يمكن حل مسألة الحد الأدنى لعدد المنصات دون ترتيب؟

نعم، لأن كل مرة تتوافق مع ساعة ثابتة. أنشئ مصفوفة من 2401 عدّادًا مفهرسة برقم HHMM ، وأضف 1 عند كل وصول واطرح 1 عند departure + 1 . أكبر مجموع تراكمي هو الإجابة: زمن O(n + 2400) . الفهارس مثل 1260 إلى 1299 ليست أوقاتًا على الساعة ولا يصل إليها أحد، لذا لا تحدد أبدًا قيمة قصوى.

متوسطالترتيب الخوارزميات الجشعة مؤشران

+10

لدى محطة جدول مواعيد ليوم واحد: يصل القطار i في arrival[i] ويغادر في departure[i]. الأوقات أرقام بصيغة HHMM، أي وقت الساعة من دون النقطتين، لذا 930 تعني 09:30.

يشغل القطار رصيفه من دقيقة وصوله حتى دقيقة مغادرته، وكلتاهما مشمولتان. لذلك، لا يمكن لقطار يصل في الدقيقة التي يغادر فيها قطار آخر أن يستخدم رصيف ذلك القطار.

أعِد أقل عدد من الأرصفة التي تحتاج إليها المحطة حتى لا يضطر أي قطار إلى الانتظار.

الدالة

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: وقت وصول كل قطار، كرقم بتنسيق HHMM
departureinteger-array: وقت مغادرة كل قطار، كرقم بصيغة HHMM؛ ينتمي departure[i] إلى arrival[i]
تُرجعinteger: أكبر عدد من القطارات في المحطة خلال الدقيقة نفسها، وهو أقل عدد من الأرصفة المطلوبة

القيود

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
كل وقت بصيغة HHMM هو وقت صالح: رقماه الأخيران لا يزيدان عن 59.
تسير جميع القطارات في اليوم نفسه. المصفوفات غير مرتبة.

أمثلة

المدخلات: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
المخرجات: 3
الشرح: في الساعة 15:30، تقف ثلاثة قطارات في المحطة: القطارات التي تمتد مواعيدها من 15:00 إلى 16:00، ومن 15:20 إلى 15:35، ومن 15:30 إلى 15:45. لا توجد أي دقيقة تشهد وجود أربعة قطارات، لذا تكفي 3 أرصفة.

المدخلات: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
المخرجات: 2
الشرح: يلتقي القطار الذي يصل الساعة 12:30 بالقطار الذي يغادر الساعة 12:30، ويحدث الأمر نفسه عند الساعة 13:00. في كل من هاتين الدقيقتين يوجد قطاران في المحطة، لذا فالإجابة هي 2، وليست 1.

المدخلات: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
المخرجات: 2
الشرح: يشغل القطار من 06:00 إلى 22:00 منصةً واحدة طوال اليوم. ولا تلتقي القطارات من 07:00 إلى 07:15 ومن 13:00 إلى 14:00 أبدًا، لذا تتشارك منصةً ثانية: 2.

سؤال إضافي

تصل بعض القطارات الليلية قبل منتصف الليل وتغادر بعده، لذا يكون رقم المغادرة أصغر من رقم الوصول. كيف ستحسب الأرصفة عندما يمتد الجدول الزمني عبر منتصف الليل؟

الحل

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

عُدَّ القطارات عند كل وصول

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

الفكرة

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

لا يزداد عدد القطارات الموجودة إلا عند وصول قطار، لذا فإن أكثر الدقائق ازدحامًا هي دقيقة وصول أحد القطارات. لكل قطار i، احسب عدد القطارات j التي تحقق arrival[j] ≤ arrival[i] ≤ departure[j]. كلا الشرطين يستخدمان ≤ لأن القطار يظل واقفًا على رصيفه في الدقيقة التي يغادر فيها.

يفحص كل قطار من القطارات n جميع القطارات n، لذا فإن العمل يتطلب O(n²): 25 مليون عملية فحص لأزواج من القطارات عند وجود 5000 قطار.

الخوارزمية

اضبط most = 0.
لكل قطار i، احسب عدد القطارات j التي تحقق arrival[j] ≤ arrival[i] ≤ departure[j].
إذا كان هذا العدد أكبر من most، فاحفظه.
أعِد most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

رتّب القائمتين وامسح باستخدام مؤشرين

الفكرة

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

عند التعادل، يأتي الوصول أولًا، لأن القطار المغادر يظل يشغل رصيفه خلال تلك الدقيقة. في المثال الأول، يعود العدد إلى 0 بعد المغادرة 1100، ثم تأتي حالات الوصول 1500 و1520 و1530 كلها قبل المغادرة 1535، فيبلغ العدد 3.

بعد نفاد أوقات الوصول، لا يمكن للمغادرات المتبقية إلا أن تقلّل العدد، لذا يتوقف المرور عندها. يستغرق الترتيب O(n log n)، ويستغرق المرور ما لا يزيد على 2n خطوة.

الخوارزمية

رتّب نسخة من arrival ونسخة من departure.
عيّن platforms وmost وi وj إلى 0.
ما دام i < n: إذا كان arrivals[i] ≤ departures[j]، فأضف 1 إلى platforms، وحدّث most، وحرّك i إلى الأمام.
وإلا، اطرح 1 من platforms وحرّك j إلى الأمام.
أعِد most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

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

استخدام المقارنة مع < عندما تتطلب القاعدة الشاملة استخدام ≤. في المثال الثاني، يشغل كل قطار يصل رصيف القطار المغادر في تلك الدقيقة، فينخفض العدد من 2 إلى 1.
طرح أعداد HHMM: ناتج 1300 ناقص 1259 هو 41، رغم أن الوقتين يفصل بينهما دقيقة واحدة. المقارنة بينهما آمنة، والحل يكتفي بالمقارنة.
ترتيب القطارات حسب وقت الوصول ومقارنة كل قطار بالقطار الذي يسبقه فقط. فالإقامة الطويلة، مثل الفترة من 06:00 إلى 22:00 في المثال الثالث، تتداخل مع قطارات تقع في مواضع متأخرة من القائمة.
تجاوز القطارات التي تصل وتغادر في الدقيقة نفسها. أربعة قطارات، يمكث كل منها من 10:00 إلى 10:00، تحتاج إلى أربعة أرصفة.

أسئلة شائعة3

ما هو التعقيد الزمني لمسألة الحد الأدنى من الأرصفة؟

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

ما الفرق بين مشكلة الحد الأدنى من المنصات ومشكلة قاعات الاجتماعات II؟

كلاهما يطلبان أكبر عدد من الفترات التي تتداخل في لحظة واحدة. هنا يشغل القطار رصيفه حتى الدقيقة التي يغادر فيها؛ أما في «قاعات الاجتماعات II»، فتكون القاعة متاحة لحظة انتهاء اجتماعها. في المسح، يتطلب ذلك مقارنة واحدة: عند التعادل، تعالج الوصول أولًا هنا، والاجتماع المنتهي أولًا هناك.

هل يمكن حل مسألة الحد الأدنى لعدد المنصات دون ترتيب؟

نعم، لأن كل مرة تتوافق مع ساعة ثابتة. أنشئ مصفوفة من 2401 عدّادًا مفهرسة برقم HHMM، وأضف 1 عند كل وصول واطرح 1 عند departure + 1. أكبر مجموع تراكمي هو الإجابة: زمن O(n + 2400). الفهارس مثل 1260 إلى 1299 ليست أوقاتًا على الساعة ولا يصل إليها أحد، لذا لا تحدد أبدًا قيمة قصوى.

def minimumPlatforms(arrival, departure):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

الإخراج المتوقع