تم إعداد ترجمة المقال خاصة لطلاب الدورة التدريبية "الخوارزميات للمطورين" .
هذا المقال جزء من سلسلة حول كيفية حل مشاكل الخوارزمية. بناءً على تجربتي الشخصية ، وجدت أن معظم الموارد تصف الحل ببساطة بالتفصيل. إن تفسير الخط الرئيسي للتفكير الذي يسمح بإيجاد حل فعال ، للأسف ، ليس شائعًا للغاية. لذلك ، فإن الهدف من هذه السلسلة هو وصف مسار التفكير المحتمل لحل المشكلات من نقطة الصفر.
مهمة
يجب على مدير الفندق معالجة أوامر الحجز N للموسم المقبل. يحتوي فندقه على غرف K. تحتوي معلومات الحجز على تاريخ تسجيل الوصول وتاريخ المغادرة. يريد المدير معرفة ما إذا كانت هناك غرف كافية في الفندق لتلبية الطلب.
إدخال البيانات:
- أول من أدخل قائمة بمعلومات عن وقت الوصول
- ثانيا - قائمة بمعلومات عن وقت المغادرة
- الثالث - K ، مشيرا إلى عدد الغرف
بيانات الإخراج:
- قيمة منطقية تشير إلى القدرة على حجز الغرف
خطأ يعني أن الفندق لا يحتوي على غرف كافية للحجوزات N
صحيح يعني أن الفندق يحتوي على غرف كافية للحجوزات N
مثال:
إدخال البيانات:
- تسجيل الوصول = [1 ، 3 ، 5]
- المغادرة = [2 ، 6 ، 10]
- ك = 1
الإخراج: خطأ. في اليوم = 5 ، يوجد بالفندق ضيفان. لكن ليس لدينا سوى رقم واحد.
عملية اتخاذ القرار
هذه المهمة مثيرة للاهتمام ، في رأيي ، لأن هناك العديد من الطرق المختلفة لحلها. دعنا ننظر إلى الخيارات.
هيكل يقوم بتخزين العدادات لكل يوم
قد تكون الفكرة الأولى هي أننا نحتاج إلى هيكل لتخزين عدد الطلبات لكل يوم. يمكن أن تكون هذه البنية صفيفًا ذو حجم ثابت (يتم تحديده بواسطة الحد الأقصى ليوم المغادرة).
إدخال البيانات:
- الإدخالات = [1 ، 3 ، 5]
- المغادرة = [2 ، 6 ، 10]
- ك = 1
في هذا المثال ، سيكون حجم المصفوفة 10 (لأن آخر خروج في اليوم 10). لملء هذه المجموعة ، نذهب إلى قوائم الإدخالات والمخارج ونزيد أو نخفض العداد في اليوم المقابل. مثال على الكود الزائف:
int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- }
نتيجة لذلك ، حصلنا على المجموعة التالية:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10بعد امتلاء المصفوفة ، تحتاج فقط إلى المرور فيها والتحقق مما إذا كانت جميع العناصر لا تتجاوز
k (عدد الغرف).
في المثال السابق ، كان الحد الأقصى لعدد الغرف هو 1. نظرًا لأن لدينا حجزان في اليوم 5 ، نعود إلى
false .
التعقيد الزمني لهذا الحل هو O (n) ، حيث n هو عدد الحجوزات ، والمكاني هو O (m) ، حيث m هو أقصى يوم للمغادرة. ليس سيئًا من الناحية النظرية ، لكن من المحتمل تخصيص الكثير من الذاكرة لمجموعة كبيرة ، على الرغم من أن معظمها لن يتم استخدامه.
على سبيل المثال:
إدخال البيانات:
- الإدخالات = [1 ، 3 ، 5]
- المغادرة = [2 ، 10000 ، 10]
- ك = 1
في هذه الحالة ، سيتم تخصيص مجموعة من 10 آلاف عدد صحيح.
لنلقِ نظرة على الحلول الأخرى.
تخزين مجموعة الحدث
ما هي الخيارات الأخرى هناك؟ دعنا ننظر مرة أخرى إلى ما حدث مع الهيكل السابق:
: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10نرى أن بعض المعلومات مكررة. على سبيل المثال ، لا يتغير عدد الحجوزات بين 6 و 9 أيام ، حيث نعلم أنه لن يحدث شيء خلال هذه الفترة الزمنية.
يمكن أن يكون أفضل إذا تم تخزين الأحداث بدلا من ذلك؟ لنأخذ نفس المثال مرة أخرى:
إدخال البيانات:
- الإدخالات = [1 ، 3 ، 5]
- المغادرة = [2 ، 6 ، 10]
يوم 1: +1 الحجز
يوم 2: -1 الحجز
يوم 3: +1 الحجز
يوم 6: -1 الحجز
يوم 5: +1 الحجز
يوم 10: -1 الحجز
الحل هو تكرار هذه الأحداث لزيادة أو تقليل العداد. إذا كان العداد في مرحلة ما أكبر من
k ، فإننا نعود
false . ومع ذلك ، من أجل التكرار ، يجب تصنيف هذه المجموعة من الأحداث.
ما الهيكل الأفضل استخدام هنا؟ لنلخص متطلباتنا:
- ابحث لمعرفة ما إذا كان هذا اليوم موجودًا بالفعل
- إضافة يوم جديد ،
- عرض هيكل لتكرار أكثر من كل يوم فرزها.
ماذا عن استخدام شجرة البحث الثنائية (BST)؟
يمكن تمثيل كل عقدة على النحو التالي:
class Node { int day int count Node left Node right }
سيتم الفرز في حقل
day .
دعونا نلقي نظرة على العواقب من حيث تعقيد الوقت:
- ابحث لمعرفة ما إذا كان مثل هذا اليوم موجودًا بالفعل: O (log (n)) في الحالة المتوسطة ، O (n) في أسوأ الحالات ،
- إضافة يوم جديد: O (log (n)) في الحالة المتوسطة ، O (n) في أسوأ الحالات ،
- عرض بنية التكرار خلال كل يوم تم الفرز: O (n) باستخدام بحث متعمق.
نظرًا لأنه يتعين علينا تكرار كل عنصر وإدراجه في الشجرة ، فإن تعقيد الخوارزمية هو O (n log (n)) في الحالة المتوسطة ، O (n²) في أسوأ الحالات.
خيار آخر هو استخدام جدول التجزئة وفرز المفاتيح بعد إضافة جميع الأحداث:
- ابحث للتحقق مما إذا كان هذا اليوم موجودًا بالفعل: O (1) في الحالة المتوسطة ، O (n) في أسوأ الحالات (يعتمد الاحتمال على قدرة المصفوفة الترابطية) ،
- إضافة يوم جديد: O (1) في الحالة المتوسطة ، O (n) في أسوأ الحالات ،
- عرض بنية التكرار على مدار كل يوم مصنفة: O (n log (n)) لمفاتيح الفرز و O (n) للفرز.
في النهاية ، يحتوي الحل على O (n log (n)) في الحالة الوسطى (بسبب عملية الفرز) ، O (n²) في أسوأ الحالات. يبدو أن هذا الحل له نفس التعقيد كحل قائم على الأشجار.
دعونا نلقي نظرة على تطبيق ممكن في جافا باستخدام صفيف النقابي فرزها:
public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { // Map<Integer, Integer> events = new HashMap<>(); // int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); // Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); // current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } // Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); // count if (count > k) { return false; } } return true; }
التعقيد المكاني الثابت
إذا كنا نريد تحسين الخوارزمية الخاصة بنا ، فعلينا التفكير فيما إذا كان من الضروري حقًا تخزين كل هذه الأحداث؟ ألا يمكننا فرز بيانات المجموعة (المدخلات والمخارج) والتحقق من حد الحجز في هذه العملية؟
الحل ممكن ، لكن من الضروري تبسيط بيانات الإدخال عن طريق فرزها مقدمًا.
إذا تم تصنيف كلتا المجموعتين ، فيمكننا ببساطة التكرار على كل عنصر باستخدام مؤشرين (واحد للمداخل والآخر للمخارج) ، والتحقق من القيود على الطاير.
كما ترون ، ما زلنا بحاجة إلى التحقق من الحد الأدنى بين كل من
arrivals.get(indexArrival) departures.get(indexDeparture) لمعرفة أي مؤشر يحتاج إلى تحديث.
بشكل عام ، تتمتع الخوارزمية بالتعقيد الزمني والمكاني الثابت O (n log (n)) بسبب عمليات الفرز.