اكتساح الخط لأقصى تداخل
عدّ الفواصل المتزامنة باستخدام الأحداث
اكتساح الخط لأقصى تداخل درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
سؤال التداخل الأقصى
كم فترة زمنية تغطي اللحظة نفسها في آن واحد؟ يمثّل العدد الأقصى للتداخل، أي أكثر نقطة ازدحامًا على مخططك الزمني. 📈
فكّر في الأحداث
توقّف عن التفكير في الفترات الزمنية كاملة. قسّم كل فترة إلى حدثين: +1 عند بدايتها و-1 عند نهايتها.
أنشئ قائمة الأحداث
أضف لكل فترة زمنية حدث بدء وحدث انتهاء إلى قائمة مشتركة واحدة. يحمل كل حدث موضعًا وقيمة تغيّر تساوي واحدًا موجبًا أو سالبًا.
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))افرز الأحداث
افرز كل حدث حسب الموضع حتى تتمكن من المسح عبر المخطط الزمني من اليسار إلى اليمين، ومعالجة التغيّرات بالترتيب الصحيح.
events.sort()امسح وعدّ
مرّ على الأحداث المفروزة مع الاحتفاظ بعدّاد تراكمي. أضف قيمة التغيّر لكل حدث عند المرور به، ويمثّل العدّاد عدد الفترات النشطة حاليًا.
active = 0
for pos, delta in events:
active += deltaتتبّع القمة
بعد كل تحديث، قارن العدّاد بأفضل قيمة وصلت إليها حتى الآن. فأكبر قيمة يبلغها العدّاد هي التداخل الأقصى.
best = max(best, active)حيلة كسر التعادل
عند تساوي المواضع، يصبح الترتيب مهمًا. إذا كان ينبغي لنهاية عند x أن تحرّر الموضع قبل بدء عند x، فافرز النهايات قبل البدايات عند النقطة نفسها.
شفّر قيم التغيّر للفرز الصحيح
من الطرق الأنيقة لكسر التعادلات اختيار قيم تغيّر تجعل فرز الصفوف ينفّذ ذلك تلقائيًا. ضع قيمة التغيّر -1 قبل +1 عندما تتطابق المواضع.
events.append((s, 1)); events.append((e, -1)) # -1 sorts first at a tieسبب السرعة
تنشئ 2n من الأحداث، وتفرزها مرة واحدة، ثم تجري مسحًا واحدًا. تعمل الطريقة بأكملها بتعقيد O(n log n)، إذ يهيمن الفرز الوحيد على التكلفة.
أين تراه
يجيب التداخل الأقصى عن مسائل شائعة مثل الحد الأدنى لعدد الغرف اللازمة للاجتماعات، أو ذروة عدد المستخدمين المتزامنين على خادم.
أبعد من مجرد العدّ
يمكن توسيع المسح نفسه بسهولة: تتبّع إجمالي الطول المغطى، أو اعثر على كل موضع يتغيّر فيه العدد، وكل ذلك في تمريرة خطية واحدة.
تحقق سريع
تجري مسحًا على الأحداث للعثور على التداخل الأقصى.
مراجعة
حوّل الفترات الزمنية إلى أحداث بدء بقيمة +1 وأحداث انتهاء بقيمة -1، ثم افرزها وامسحها باستخدام عدّاد للعثور على القمة. اكسر التعادلات بتقديم الانتهاء على البدء. 🚀
الأسئلة الشائعة
هل درس «اكتساح الخط لأقصى تداخل» مجاني؟
نعم — نص درس «اكتساح الخط لأقصى تداخل» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «اكتساح الخط لأقصى تداخل»؟
عدّ الفواصل المتزامنة باستخدام الأحداث تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «اكتساح الخط لأقصى تداخل»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- ترتيب الفواصل حسب البداية
- دمج الفواصل المتداخلة
- اكتساح الخط لأقصى تداخل
- أقل عدد من الإزالات لمنع التداخل