دمج الفواصل المتداخلة

عند إعطائكم فترات كثيرة، تريدون دمج الفترات المتلامسة أو المتداخلة في أقل عدد ممكن من النطاقات غير المتداخلة. 🧩

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

لا ينجح الدمج من اليسار إلى اليمين إلا إذا كانت الفترات مرتبة، لذا ابدؤوا بترتيبها حسب البداية. وهذا هو أساس عملية المرور كلها.

مرّروا على القائمة المرتبة مع الاحتفاظ بفترة مدمجة حالية واحدة. فإما أن تمددها كل فترة جديدة، أو تبدأ نطاقًا جديدًا.

إذا كانت البداية التالية ضمن النطاق الحالي، فهناك تداخل؛ لذا مدّدوا النهاية الحالية إلى الأكبر بين النهايتين.

استخدموا دائمًا max للنهاية الجديدة. فالفترة القصيرة الواقعة داخل فترة طويلة يجب ألا تصغّر النطاق الذي بنيتموه.

إذا تجاوزت البداية التالية النهاية الحالية، فهناك فجوة. أضيفوا النطاق المكتمل إلى إجابتكم وابدؤوا فترة حالية جديدة.

تبني الحلقة النطاق الأخير لكنها لا تضيفه. بعد انتهاء الحلقة، نفّذوا append للفترة الحالية الأخيرة حتى لا تضيع.

حدّد ما إذا كان ينبغي دمج [1, 3] و[3, 5]. يحدث ذلك عادةً، لذا استخدم start <= cur_end. اقرأ نص المسألة للتأكد من قاعدة الحافة هذه.

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

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

تدمج الفترات الزمنية بعد فرزها حسب وقت البدء.

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