ما خوارزمية لاستخدامها لهذه المشكلة؟

Question

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

مشكلة

نريد تنظيم حدث مع أكبر قدر ممكن من الأداء. نحصل على قائمة بأوقات وصول الأداء المحتملة ومتركات الأداء. يجب أن تعيد وظيفتنا الحد الأقصى لعدد الأداء الذين يمكن اختيارهم دون تعارضات.

مثال

n= 5
القادمون= [1، 3، 3، 5، 7] (يصل فنون الأداء في هذه الأوقات)
فترات= [2، 2، 1، 2، 1] (الوقت اللازم لإنهاء عروضها)
الحل= 4

لذلك في الوقت المناسب 1 يمكننا قبول الأداء وسوف ينتهي في وقت 3. في الوقت 3 لدينا خيارات اثنين من الخيارات المتضاربة، ولا يهم الذي اخترناه. الوقت 5 و 7 غير متضارب أيضا.

حلاي

1. قدمت tuples من الوافدين والممور عن طريق الزلزال. فرز tuples أولا عند الوصول، ثم مدة.
2. الخارجي لدورة لأني من البداية إلى النهاية. تهيئة مجموعة جديدة في كل ITER.
3. الداخلية للدورة ل J من أنا لإنهاء. تحقق ما إذا كان يمكن إضافة J إلى المجموعة دون تعارض. إذا كانت المجموعة أطول من الحد الأقصى الذي أحفظه.

مصدر بيثون

أسئلة

1. هل هناك طرق أفضل، خوارزميات قياسية لحل هذه المشكلة؟
2. أعرف أن هناك بعض حالات الحافة، والتي لا تعمل خوارزمية. قام Hackerrank بتقييم Algo Algo، وأمرت فقط بحالات اختبار 7/13. ما يمكن أن يكون بعض الحالات الحافة أنا في عداد المفقودين؟
3. هل هذه مشكلة البحث أو مشكلة تحسين؟

Answer 1

هذا هو بسيط الجدولة الفاصل الزمني تعظيم مشكلة، والتي يمكن حلها في < EM> O (N Log (n)) الوقت عبر خوارزمية بسيطة الجشع. الحيلة هي فرز العروض وفقا لوقت نهاية وليس وقت البدء .

هنا هو وصف الحل الموجود في صفحة ويكيبيديا التي ربطتها:

---

العديد من الخوارزميات، والتي قد تبدو واعدة من النظرة الأولى، في الواقع لا تجد الحل الأمثل:

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

• اختيار أقصر فترات أو اختيار فترات مع عدد أقل من الصراعات ليست هي أيضا الأمثل.

حل متعدد الحدود الجشع

الخوارزمية الجشعة التالية لا تجد الحل الأمثل:

giveacodicetagpre.

كلما اخترنا فاصل فاصل في الخطوة 1، قد يتعين علينا إزالة العديد من الفواصل الزمنية في الخطوة 2. ومع ذلك، فإن كل هذه الفواصل الزمنية تعبر بالضرورة وقت التشطيب من X، وبالتالي فإنهم جميعا يعبرون بعضهم البعض. وبالتالي، يمكن أن تكون على الأكثر من هذه الفواصل في الحل الأمثل. وبالتالي، لكل فاصل في الحل الأمثل، هناك فاصل زمني في الحل الجشع. هذا يثبت أن الخوارزمية الجشعة وجدت بالفعل حلا الأمثل.

يتم إعطاء شرح رسمي أكثر من قبل حجة الشحن .

يمكن تنفيذ الخوارزمية الجشع في الوقت المناسب o (n تسجيل الدخول n) ، حيث n هو عدد المهام، باستخدام خطوة مسبقة مسبقا التي يتم فيها فرز المهام من خلال مرات التشطيب.

---

Answer 2

إلقاء نظرة على الحد الأقصى لجدولة الفاصل الزمني .

قم بتعيين الفاصل الزمني $ (s_i، t_i) $ إلى كل أداء، ل $ i= 1، \ dots، N $ ، مما يعني أن الأداء يبدأ في الوقت $ s_i $ ولديها مدة $ t_i - s_i $ .

افترض الآن أن جميع الفواصل الزمنية يتم فرزها من خلال وقتهم النهائي. فقط للبساطة افترض أيضا أن جميع الأوقات متميزة (هذا الافتراض غير ضروري). ثم يمكن حل مشكلتك في $ O (n) $ الوقت.

النظر في $ (s_1، t_1) $ ودع $ i $ $ كن مجموعة من الفواصل الزمنية التي تتقاطع (باستثناء $ (s_1، t_1) $ نفسها).

من السهل أن نرى أن جميع الفواصل الزمنية في $ I $ يجب أن تبدأ قبل $ t_1 $ ( كما أنها لن تتقاطع $ (s_1، t_1) $ ) وتنتهي بعد $ t_1 $ ( خلاف ذلك $ T_1 $ لن يكون الحد الأدنى للوقت). هذا يعني أن جميع الفواصل الزمنية في $ i \ cup \ {(s_1، t_1) $ interersect مع بعضها البعض وبالتالي يمكن أن يحتوي أي حل على الأكثر منهم.

دع $ S $ كن حلا (I.E.، مجموعة فرعية من الفواصل الفرعية غير المتقاطعة الزوجية). من الممكن دائما تحويل $ S $ في حل جديد $ S $ يحتوي على $ (s_1، t_1) $ و مثل ذلك $ | \ GE | S | $ .

إذا كان $ s \ cap i=expryset $ ثم نفعلها بشكل تافه لأنه يمكننا اختيار $ s '= S \ cup \ {(s_1، t_1) $ (لاحظ أن هذا يتضمن أيضا الحالة التي $ (s_1، t_1) \ in s $ ).

إذا كان $ s \ cap i \ neq \ expryset $ ، دع $ (s_i، t_i) $ أن تكون الفاصل الزمني الفريد في $ s \ cap i $ . أي الفاصل الزمني $ (s_j، t_j) \ in s \ setminus \ {(s_i، t_i) \} $ يجب أن ترضي إما $ s_j> t_i> t_1 $ أو $ s_i> t_j> t_1 $ . الحالة الأخيرة مستحيلة فعلا لأنها ستتناقض مع حقيقة أن $ (s_i، t_i) \ in s $ . بمعنى آخر، إذا استبدلنا $ (s_i، t_i) $ مع $ (s_1، t_1) $ ما زلنا نحصل على حل ممكن. لذلك نحن اختيار $ s '= s \ cup \ {(s_1، t_1) \} \ setminus \ {(s_i، t_i) \} $ .

الخلاصة هو أن هناك دائما الحل الأمثل يحتوي على $ (s_1، t_1) $ . لذلك يمكنك دائما إضافة $ (s_1، t_1) $ إلى حلكم، حذف جميع الفواصل الزمنية في $ s \ cup \ { (s_1، t_1) \} $ ، والبحث عن الحل الأمثل بين الفواصل الزمنية المتبقية. هذه المبالغ لتشغيل الخوارزمية الجشعة التي تعتبر الفواصل الزمنية من أجل ويضيف أي فاصل يناسب.

من مثيلك، يبدو أن أوقات البدء مصنفة بالفعل. في هذه الحالة، يمكنك القيام بحيلة "عكس الوقت"، أي تبديل أوقات البدء والنهاية، على سبيل المثال عن طريق تغيير $ (s_i، t_i) $ في $ (- t_i، -s_i) $ ، والذي يسمح لك بالحصول على $ O (n) $ - خوارزمية الوقت من خلال تخطي خطوة الفرز الأولي التي ستطلب بالفعل $ \ Omega (n \ log n) $ الوقت.