اختيار المواعيد غير المتداخلة: ابدأ بالأقرب انتهاءً

تطلب جدولة الفترات أكبر عدد متوافق من مواعيد ثابتة، دون تحريك بداياتها أو نهاياتها. [1]

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

الخلاصة السريعة

• رتب المواعيد بحسب وقت النهاية، واقبل الموعد إذا كانت بدايته لا تسبق نهاية آخر موعد مقبول. [2]
• في مثالنا يختار الفحص B،C،E،G، وهي أربعة مواعيد. البدء بالأقدم بداية يعطي A،G فقط.
• نمثل الموعد بفترة نصف مفتوحة [s,f): يمكن أن يبدأ التالي لحظة انتهاء السابق، ونشترط s<f.
• فحص البرنامج كل مجموعة فرعية في المثال، ثم اختبر 4944 عائلة صغيرة أخرى؛ تطابق عدد الاختيار مع الحد الأقصى المحصور.
• تعظيم العدد لا يعني تعظيم الإيراد أو وقت تشغيل الجهاز؛ تغيير الهدف يحتاج إعادة تعريف المسألة.

اكتب شرط التوافق قبل ترتيب القائمة

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

لذلك يكون الموعدان [1,3) و[3,5) متوافقين: الأول يترك الجهاز عند الثالثة والثاني يبدأ عندها. لو اشترط العمل مهلة تجهيز، فلن تكفي هذه الحدود كما هي. يجب تمثيل المهلة في نموذج الحجز قبل تشغيل المقارنة.

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

مر على المواعيد بحسب النهاية

قائمتنا هي A=[0,7)، وB=[1,3)، وC=[3,5)، وD=[4,6)، وE=[5,8)، وF=[6,9)، وG=[8,10)، وH=[9,11). لا نخلط ترتيب الحروف بترتيب الفحص.

افحص بحسب النهاية؛ اقبل البداية التي لا تسبق نهاية آخر فترة مقبولة. [2]

نرفض D لأن بدايتها الرابعة تسبق نهاية C الخامسة. رفضها لا يحرك الحد إلى السادسة: آخر موعد مقبول ما زال C. هذه نقطة تنفيذية مهمة؛ تحديث الحد عند كل سطر، حتى المرفوض، سيمنع قبول مواعيد صالحة لاحقًا.

بعد قبول E يصير الحد ثمانية، فنرفض F التي تبدأ عند ستة. تصل G عند ثمانية تمامًا فتقبل. الناتج أربع فترات متتابعة من الواحدة إلى العاشرة، ولا توجد فجوة في هذه السلسلة الخاصة.

لماذا لا نخسر حلًا أفضل باختيار النهاية الأقرب؟

سمِّ أول فترة في حل أقصى o، واختيار القاعدة g. استبدال o بـg يحفظ العدد والتوافق؛ لأن g تنتهي قبلها أو معها. تكرار الحجة على الباقي يعطي حلًا أقصى يبدأ باختياراتنا. [2]

في سجلنا تبدأ الحجة باختيار B المنتهي عند ثلاثة. أي سلسلة أمثل تبدأ بموعد ينتهي لاحقًا لا تمنح المواعيد الباقية مساحة إضافية إلى اليمين مقارنة باستبدال أولها بـB. بعد تثبيت B نعيد السؤال بين المواعيد التي تبدأ عند ثلاثة أو بعدها، لا بين جميع السطور من البداية.

قد يوجد أكثر من حل أقصى للعدد نفسه. فمثلًا السلسلة B،D،F،H صالحة أيضًا وفيها أربعة مواعيد، لكنها تنتهي عند أحد عشر. المطلوب إثبات الوصول إلى أكبر عدد، لا أن القائمة التي أخرجناها هي الحل الوحيد.

مثالان يكشفان قصور قواعد أخرى

إذا رتبنا قائمتنا بحسب البداية، نقبل A=[0,7) أولًا. يمنع ذلك B وC وD وE وF. ثم نقبل G=[8,10)، ونرفض H. نصل إلى موعدَين بدل أربعة. البدء قبل الآخرين لا يعني ترك الجهاز للموعد التالي قبلهم.

ولفحص قاعدة المدة الأقصر، نستعمل مثالًا جديدًا أصغر: J=[0,4)، وK=[4,8)، وL=[3,5). أقصر مدة هي L بطول اثنين، لكنها تتداخل مع كل من J وK. قبولها يترك موعدًا واحدًا، بينما يقبل اختيار J ثم K موعدَين.

تنفيذ قصير مع شروط المدخلات

def select_intervals(rows):
    chosen = []
    last_finish = None
    for name, start, finish in sorted(rows, key=lambda r: (r[2], r[1], r[0])):
        if start >= finish:
            raise ValueError("positive duration required")
        if last_finish is None or start >= last_finish:
            chosen.append(name)
            last_finish = finish
    return chosen

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

اسمان مختلفان للفترة [1,3) لا يجعلانها حجزين متوافقين؛ بعد قبول أحدهما يبدأ الآخر قبل الحد ثلاثة فيُرفض. وترفض الشفرة فترة طولها صفر بدل خلطها بمواعيد إيجابية المدة. إن كانت المواعيد اللحظية مقصودة، فيجب تحديد معناها وتوافقها أولًا.

قارن الناتج بحصر مستقل

فحصنا المجموعات الفرعية للمثال الثماني جميعها، وعددها 2⁸=256. في كل مجموعة قارنا كل زوج مباشرة: يكونان متوافقين إذا انتهت الأولى قبل بداية الثانية أو عندها، أو بالعكس. أكبر عدد وجدناه أربعة، موافقًا لاختيار الفرز.

ثم أنشأنا الفترات الموجبة ذات الطرفين الصحيحين بين صفر وخمسة: عددها خمسة عشر. اختبرنا جميع العائلات التي تضم صفرًا إلى خمس فترات متميزة منها، وعددها 1+15+105+455+1365+3003=4944. لكل عائلة قارنا طول ناتج القاعدة بأفضل عدد عبر جميع مجموعاتها الفرعية. نجحت المقارنات كلها.

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

غيّر الهدف فتتغير الإجابة المطلوبة

إذا حملت كل فترة قيمة مختلفة، تصبح المسألة الموزونة طلب أكبر مجموع قيم لفترات غير متداخلة. هذا هدف مختلف عن أكبر عدد، وتعرضه محاضرات كورنيل ضمن البرمجة الديناميكية. [3]

نختار مثالًا صغيرًا يوضح الفرق: U=[0,2) بقيمة واحد، وV=[2,4) بقيمة واحد، وW=[0,4) بقيمة تسعة. قاعدة العدد تقبل U وV، وقيمتهما معًا اثنان. اختيار W وحده يعطي تسعة. إذن نجاح القاعدة في تعظيم العدد لا يبرر وصف ناتجها بأنه أعلى قيمة.

إذا احتجت سفرًا بين المواقع، تتغير الشروط أيضًا. راجع مثال مسار التسليم ونوافذ الوقت لفهم دخول السفر والانتظار في الفحص. في التطبيق الحالي تكفي بدايات ثابتة ونهايات ثابتة وجهاز واحد وهدف العد؛ احفظ هذه الشروط بجانب النتيجة كي يستطيع شخص آخر إعادة التحقق منها.

المصادر

1. Cornell CS 4820 — Interval Scheduling: تعريف هدف اختيار أكبر عدد.
2. Princeton COS 423 — Greedy Algorithms I، الشرائح 9–14: قاعدة أقرب نهاية وحجة الاستبدال.
3. Cornell CS 4820 — Weighted Interval Scheduling: هدف مجموع القيم.

الفترات والرسوم والحصر البرمجي أصلية لهذا المقال، ولم يُنفذ حجز فعلي. أُعدت الصياغة والمراجعة الأولية بمساعدة الذكاء الاصطناعي، دون ادعاء مراجعة خبير بشري مستقل.