Job Sequencing Problem

Q: ما هو التعقيد الزمني لمشكلة جدولة المهام؟

باستخدام مجموعة منفصلة، يكون الزمن O(n log n) ، ويهيمن عليه الفرز، والمساحة O(n) . أما البحث عكسيًا من كل موعد نهائي عن خانة شاغرة، فتبلغ كلفته O(n²) عندما تكون معظم المواعيد النهائية كبيرة.

متوسطالخوارزميات الجشعة الترتيب

+10

لديك n وظيفة ممثلة بمصفوفتين: تحقق الوظيفة i ربحًا قدره profit[i] إذا انتهت بحلول الوقت deadline[i]. تستغرق كل وظيفة وحدة زمنية واحدة، وتنفذ وظيفة واحدة في كل مرة بدءًا من الوقت 0، ويمكنك تخطي أي وظيفة. يمكن تنفيذ وظيفة موعدها النهائي 2 من 0 إلى 1 أو من 1 إلى 2.

أعِد أكبر ربح إجمالي يمكنك تحقيقه.

الدالة

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: الوقت الذي يجب أن تُنجَز فيه كل مهمة، من 1 إلى n
profitinteger-array: ما تكسبه كل مهمة؛ profit[i] مرتبط بـ deadline[i]
تُرجعinteger: أكبر إجمالي ربح للوظائف التي يمكن أن تنتهي جميعها بحلول مواعيدها النهائية

القيود

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n، حيث إن n هو عدد المهام
1 ≤ profit[i] ≤ 10⁵
المصفوفات غير مرتبة. قد تتشارك عدة مهام الموعد النهائي أو الربح.

أمثلة

المدخلات: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
المخرجات: 120
الشرح: لا تتسع المهلة 1 إلا لمهمة واحدة من المهمتين، لذا نفّذ المهمة التي قيمتها 50. ثم تنتهي المهمة التي قيمتها 30 عند موعدها النهائي 2، والمهمة التي قيمتها 40 عند موعدها النهائي 3: 50 + 30 + 40 = 120.

المدخلات: deadline = [1, 1, 1]profit = [5, 9, 7]
المخرجات: 9
الشرح: يجب أن تنتهي المهام الثلاث كلها بحلول الوقت 1، ولا تتسع الفترة لما قبل ذلك إلا لمهمة واحدة. وأفضلها تكسب 9.

سؤال إضافي

ماذا لو كانت المهمة i تستغرق duration[i] وحدة زمنية بدلًا من وحدة واحدة؟ هل يظل إنجاز المهمة الأكثر ربحًا أولًا يؤدي إلى أفضل إجمالي؟

الحل

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

نهج جشع حسب الربح، مع البحث عن خانة شاغرة

الفكرة

قسّم الزمن إلى فترات: الفترة t تمتد من t-1 إلى t، ويمكن لوظيفة موعدها النهائي d استخدام الفترات من 1 إلى d، ولا يتجاوز أي موعد نهائي n. اختيار الوظيفة الأعلى ربحًا أولًا آمن: إذا كانت كل الفترات التي يمكنها استخدامها محجوزة، فإن استبدالها بالوظيفة الموجودة في إحداها يحقق ربحًا لا يقل عنها. كما أن حجز أحدث فترة ممكنة آمن، لأن الفترات المبكرة هي الوحيدة التي يمكن للوظائف ذات المواعيد النهائية القصيرة استخدامها.

التكلفة تكمن في البحث. عندما يكون الموعد النهائي لكل وظيفة هو n، تتجاوز الوظيفة رقم k عدد k-1 من الفترات المحجوزة: أي نحو n²/2، أو 12.5 مليون خطوة عندما n = 5000.

الخوارزمية

رتّب الوظائف حسب الربح، من الأكبر إلى الأصغر، مع إبقاء كل موعد نهائي مرتبطًا بربحه.
أنشئ مصفوفة taken من n + 1 راية، جميعها false.
لكل وظيفة، ابدأ من موعدها النهائي وقلّل t حتى 1، وتوقّف عند أول خانة غير مأخوذة.
إذا وجدت خانة، فاجعلها مأخوذة وأضف ربح الوظيفة إلى total.
أعِد total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

الخوارزمية الجشعة حسب الربح باستخدام مجموعة منفصلة من الفترات الزمنية المتاحة

الفكرة

يمرّ الفحص على الخانات المحجوزة نفسها مرارًا وتكرارًا. وتُستخدم بنية المجموعات المنفصلة على الخانات من 0 إلى n لتجاوزها: تكون parent[t] = t ما دامت الخانة t فارغة، وعند حجزها تصبح parent[t] = t-1، لذا فإن تتبّع المؤشرات انطلاقًا من موعد نهائي يوصلك إلى أحدث خانة فارغة. والوصول إلى الخانة 0 يعني أنه لم يتبقَّ شيء. ويجعل ضغط المسار كل خانة تمرّ بها تشير إلى خانة تبعد خطوتين إلى الأمام، فتكون عمليات التتبّع اللاحقة أقصر.

في المثال الثالث، تحجز المهمتان اللتان تبلغ قيمتهما 60 و50 الخانتين 2 و1. أما المهمة التي تبلغ قيمتها 20 وموعدها النهائي 2، فتتبع المسار من 2 إلى 1 ثم إلى 0، ولذلك يتم تجاوزها.

يستغرق الفرز O(n log n)، ومع ضغط المسار، يستغرق كل استعلام O(log n) بالتوسّط، لذا يبقى الإجمالي O(n log n).

الخوارزمية

رتّب الوظائف حسب الربح، من الأكبر إلى الأصغر، مع إبقاء كل موعد نهائي مرتبطًا بربحه.
عيّن parent[t] = t لكل خانة t من 0 إلى n.
لكل وظيفة، ابدأ عند slot = deadline واتبع parent حتى يصبح parent[slot] == slot، مع تقصير المسار أثناء ذلك.
إذا كان slot > 0، فأضف ربح الوظيفة وعيّن parent[slot] = slot-1؛ وإلا فتجاوز الوظيفة.
أعِد الإجمالي.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

أخطاء شائعة وحالات حدّية

وضع المهمة في أسبق خانة شاغرة. في المثال الثالث، ستشغل المهمة التي ربحها 60 الخانة 1، وستُفقد المهمة التي ربحها 50: 80 بدلًا من 110.
اختيار المهام حسب ترتيب المواعيد النهائية. مع المواعيد النهائية [1, 1] والأرباح [1, 100]، ستشغل المهمة الأقل ربحًا الخانة الوحيدة، وستكسب 1 بدلًا من 100.
جعل حجم مصفوفة الخانات n بدلًا من n + 1. عندها، ستؤدي قراءة موعد نهائي يساوي n إلى تجاوز نهاية المصفوفة.
ترتيب الأرباح وحدها. يجب أن يتحرك كل موعد نهائي مع ربحه.
كتابة خطوة البحث باستخدام الاستدعاء الذاتي. قد تؤدي سلسلة تمر عبر آلاف الخانات المحجوزة إلى تجاوز سعة المكدس؛ استخدم حلقة.

أسئلة شائعة3

ما هو التعقيد الزمني لمشكلة جدولة المهام؟

باستخدام مجموعة منفصلة، يكون الزمن O(n log n)، ويهيمن عليه الفرز، والمساحة O(n). أما البحث عكسيًا من كل موعد نهائي عن خانة شاغرة، فتبلغ كلفته O(n²) عندما تكون معظم المواعيد النهائية كبيرة.

لماذا تنجح الطريقة الجشعة في جدولة الوظائف؟

تتضمن بعض الجداول المثلى المهمةَ الأعلى ربحًا. إذا استُبعدت وكان هناك وقت شاغر قبل موعدها النهائي، فإن إضافتها تحقق ربحًا أكبر؛ وإذا كانت جميع الأوقات المتاحة محجوزة، فإن استبدال إحدى المهام بها يحقق ربحًا لا يقل عن ذلك. وتتكرر الحجة مع المهام المتبقية.

هل يمكن حلّ مسألة جدولة الوظائف باستخدام كومة بدلًا من ذلك؟

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

def jobSequencing(deadline, profit):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

الإخراج المتوقع