ترتيب الفواصل حسب البداية

الفترة interval هي ببساطة زوج من الأعداد: بداية ونهاية، مثل [2, 5]. ومعظم مسائل الفترات تتكون من قائمة بهذه الأزواج. 📏

تصل الفترات الأولية بأي ترتيب، مما يصعّب تحليلها. ويحوّل ترتيبها أولًا هذه الفوضى إلى مرور واضح من اليسار إلى اليمين.

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

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

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

عندما تتشارك فترتان في البداية، يحدد المفتاح الثانوي ترتيبهما. ويضع الترتيب حسب (start, end) الفترات الأقصر أولًا، وهو ما يساعد غالبًا.

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

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

إذا كانت كل فترة تحمل معرّفًا أو وزنًا، فرتّبوا السجل كاملًا، لا الحدود وحدها. فالمفتاح يتحكم في الترتيب بينما ترافقه البيانات.

تتبع خوارزمية الفترات تقريبًا النمط رتّب أولًا، ثم مرّر. اضبطوا الترتيب، وستصبح عمليات الدمج والعد والجدولة حلقات بسيطة.

تخيلوا الفترات كضيوف يصلون إلى حفلة. يؤدي ترتيبها حسب البداية إلى تنظيمها وفق وقت الوصول حتى تتمكنوا من استقبالهم واحدًا تلو الآخر.

أنتم على وشك دمج قائمة من الفترات.

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