أقل عدد من الإزالات لمنع التداخل
الجدولة الجشعة بالاحتفاظ بالأبكر انتهاءً
أقل عدد من الإزالات لمنع التداخل درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
هدف الحذف
لديك فترات زمنية متداخلة، وتريد أقل عدد من عمليات الحذف حتى لا يعود بينها أي تداخل. احتفظ بأكبر عدد ممكن منها. ✂️
اعكس صياغة المسألة
حذف أقل عدد ممكن يعادل الاحتفاظ بأكبر عدد من الفترات الزمنية غير المتداخلة. حلّ نسخة الاحتفاظ، ثم يكون عدد عمليات الحذف هو n ناقص عدد الفترات المحتفظ بها.
هذه مسألة اختيار الأنشطة
الاحتفاظ بأكبر عدد من الفترات الزمنية غير المتداخلة هو في حقيقته مسألة اختيار الأنشطة الكلاسيكية. وتحل الفكرة الجشعة نفسها المسألتين.
الفرز حسب النهاية
الترتيب الفائز هنا يكون حسب وقت الانتهاء، لا البدء. فالانتهاء مبكرًا يحرّر المخطط الزمني بأسرع وقت للفترة التالية التي قد تحتفظ بها.
intervals.sort(key=lambda x: x[1])الاختيار الجشع
احتفظ دائمًا بالفترة الزمنية التي تنتهي أبكر من بين الفترات المتوافقة حتى الآن. فهذا يترك أكبر مساحة ممكنة لبقية الفترات.
تتبّع نهاية آخر فترة محتفظ بها
احتفظ بنهاية آخر فترة زمنية أبقيت عليها. ولا تكون الفترة التالية متوافقة إلا إذا كان وقت بدئها عند الحد الفاصل أو بعده.
if start >= last_end:
last_end = endاحسب عمليات الحذف
عندما تبدأ فترة زمنية قبل last_end، فإنها تتعارض مع الفترة السابقة، لذا تستبعدها وتزيد عدّاد عمليات الحذف بمقدار واحد. وإلا فاحتفظ بها.
else:
removed += 1سبب فوز النهاية الأبكر
يثبت ذلك برهان الاستبدال: فاستبدال أي فترة محتفظ بها بالفترة المتوافقة ذات النهاية الأبكر لا يقلّل أبدًا من عدد الفترات التي يمكنك الاحتفاظ بها.
تعامل مع حالة التلامس
حدّد ما إذا كان [1, 2] و[2, 3] يُعدّان متداخلين. فإذا كان الاشتراك في نقطة النهاية فقط مسموحًا، فاستخدم start >= last_end كاختبار لك.
الخوارزمية الجشعة كاملة
افرز حسب النهاية، وامسح مرة واحدة، واحسب التعارضات. تبلغ التكلفة الإجمالية O(n log n) بسبب الفرز، إضافة إلى تمريرة خطية واحدة.
removed = 0; last_end = float('-inf')
for s, e in intervals:
if s >= last_end: last_end = e
else: removed += 1نمط مألوف
يُستخدم هذا النمط لجدولة أكبر عدد من الاجتماعات في غرفة واحدة أو لجدولة أكبر عدد من المهام على جهاز واحد. تعرّف عليه متى وجب تقليل التعارضات.
تحقق سريع
تحتفظ جشعًا بالفترات الزمنية غير المتداخلة.
مراجعة
يساوي الحد الأدنى لعمليات الحذف n ناقص أكبر عدد يمكنك الاحتفاظ به. افرز حسب النهاية، واحتفظ جشعًا بالفترات المتوافقة ذات النهايات الأبكر، ثم احسب الباقي. 🚀
الأسئلة الشائعة
هل درس «أقل عدد من الإزالات لمنع التداخل» مجاني؟
نعم — نص درس «أقل عدد من الإزالات لمنع التداخل» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «أقل عدد من الإزالات لمنع التداخل»؟
الجدولة الجشعة بالاحتفاظ بالأبكر انتهاءً تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.
كم من الوقت يستغرق درس «أقل عدد من الإزالات لمنع التداخل»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- ترتيب الفواصل حسب البداية
- دمج الفواصل المتداخلة
- اكتساح الخط لأقصى تداخل
- أقل عدد من الإزالات لمنع التداخل