اختيار الأنشطة حسب أقرب وقت انتهاء

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

يتعارض نشاطان إذا بدأ أحدهما قبل انتهاء الآخر. ولا يمكنك اختيار سوى نشاط واحد من أي زوج متداخل.

تتمثل الفكرة الجشعة الأساسية في اختيار النشاط الذي ينتهي أولًا من بين الأنشطة المتاحة. فالانتهاء المبكر يترك أكبر مساحة للأنشطة الأخرى.

ابدأ بعملية فرز جميع الأنشطة حسب وقت انتهائها. عندها يصبح أفضل اختيار تالٍ ببساطة هو النشاط التالي في هذا الترتيب الذي لا يتعارض.

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

مرّ على القائمة المرتبة مرة واحدة. إذا كان النشاط يبدأ عند last_end أو بعده، فاختره وحدّث last_end إلى وقت انتهائه.

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

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

قد يؤدي الاختيار حسب البدء المبكر إلى اختيار نشاط طويل يستحوذ على اليوم كله. كما قد يضللك الاعتماد على المدة وحدها، لذا ثق بوقت الانتهاء.

حدّد ما إذا كان انتهاء نشاط في اللحظة التي يبدأ فيها نشاط آخر يُعد تعارضًا. استخدم s >= last_end للسماح بأنشطة متتالية مباشرة.

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

تريد الحصول على أكبر عدد من الأنشطة غير المتداخلة.

رتّب الأنشطة حسب وقت الانتهاء، ثم اختر كل نشاط يبدأ بعد انتهاء آخر نشاط اخترته. وتمنحك عملية فرز واحدة ومرور واحد أكبر مجموعة ممكنة. 🚀