Non-overlapping Intervals
تحصل على قائمة من الفترات الزمنية على شكل مصفوفتين: تمتد الفترة i من starts[i] إلى ends[i]. احذف أقل عدد ممكن من الفترات بحيث لا تتداخل أي فترتين من الفترات المتبقية. الفترتان اللتان تتلامسان فقط، بحيث تنتهي إحداهما عند النقطة نفسها التي تبدأ عندها الأخرى، لا تتداخلان.
اكتب دالة باسم eraseOverlapIntervals تُعيد أصغر عدد من الفترات التي عليك حذفها.
الدالة
- startsinteger-array
- بداية كل فترة زمنية
- endsinteger-array
- نهاية كل فترة، عند الفهرس نفسه الذي تبدأ عنده
- تُرجعinteger
- أقل عدد من الفترات الزمنية التي يجب حذفها حتى لا تتداخل الفترات المتبقية
القيود
1 ≤ starts.length == ends.length ≤ 5000-5 × 104 ≤ starts[i] < ends[i] ≤ 5 × 104- الفترات غير مرتبة. قد تكون فترتان متطابقتين.
أمثلة
- المدخلات
- starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
- المخرجات
- 2
- الشرح
- بترتيب البداية، الفترات هي [1,4] و[2,3] و[3,6] و[5,7]. احتفظ بالفترتين [2,3] و[3,6]، اللتين تتلامسان فقط، واحذف الفترتين الأخريين. لا يمكنك الاحتفاظ بثلاث فترات: فالفترة [1,4] تتداخل مع [2,3]، والفترة [3,6] تتداخل مع [5,7]، وأي ثلاث فترات من الأربع تتضمن أحد هذين الزوجين.
- المدخلات
- starts = [0, 0, 0]ends = [5, 5, 5]
- المخرجات
- 2
- الشرح
- الفترات الثلاث كلها [0,5]، لذا فإن أي فترتين منها تتداخلان. يمكن الإبقاء على واحدة فقط، وتحذف الفترتين الأخريين
2.
- المدخلات
- starts = [4, 1, 2]ends = [6, 2, 4]
- المخرجات
- 0
- الشرح
- تتصل الفترات [1,2] و[2,4] و[4,6] من النهاية إلى البداية ولا تتداخل أبدًا، لذا لا تحذف شيئًا وتكون الإجابة
0.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
افترض أن لكل فترة أيضًا قيمة، وأنك تريد أكبر مجموع للقيم بين الفترات التي لا تتداخل. هل يظل الاحتفاظ بالفترة التي تنتهي أولًا مجديًا؟ ما الذي ستستخدمه بدلًا من ذلك؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بدلًا من اختيار ما يجب إزالته، فكّر فيما يجب الإبقاء عليه. ما علاقة أكبر مجموعة من الفترات الزمنية التي يمكنك الإبقاء عليها بالإجابة؟
من بين جميع الفترات، تترك الفترة التي تنتهي أولًا أكبر مساحة لبقية الفترات. وتحتفظ بها دائمًا إحدى أفضل الإجابات.
رتّب الفترات حسب نهايتها، ومرّ عليها مع تذكّر نهاية آخر فترة أبقيتها. تُبقى الفترة التي تبدأ عند تلك النهاية أو بعدها؛ وتُحسب كل فترة أخرى على أنها محذوفة.
الحل
إزالة أقل عدد من الفترات تعادل الاحتفاظ بأكبر عدد من الفترات غير المتداخلة، لذا تكون الإجابة هي n ناقص حجم تلك المجموعة الأكبر. تجربة كل مجموعة للاحتفاظ بها تتطلب زمنًا أُسّيًا، ويخفضها البرمجة الديناميكية على سلاسل الفترات إلى O(n²). وتنهي قاعدة جشعة واحدة المهمة في O(n log n): من بين الفترات التي لا تزال ملائمة، احتفظ دائمًا بالفترة التي تنتهي أولًا.
أبقِ كل فترة أو أزِلها
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اقلب السؤال. إزالة أقل عدد من الفترات تعني الإبقاء على أكبر عدد من الفترات غير المتداخلة، والإجابة هي n ناقص ذلك العدد. لذا ابحث عن أكبر مجموعة يمكنك الإبقاء عليها.
رتّب الفترات حسب بدايتها، وقرّر لكل فترة، بهذا الترتيب، ما إذا كنت ستزيلها أم ستُبقيها. يمكنك إبقاؤها فقط إذا بدأت عند نهاية آخر فترة أبقيتها أو بعدها. هذا الفحص الواحد كافٍ: فالفترات التي أبقيتها تشكّل عندئذٍ سلسلة تبدأ فيها كل فترة عند نهاية الفترة السابقة أو بعدها، لذا لا تتداخل أي فترتين منها. جرّب الخيارين عند كل فترة، وخذ النتيجة الأفضل.
في المثال الأول، تكون الفترات المرتبة هي [1,4]، [2,3]، [3,6]، [5,7]. إبقاء [1,4] يمنع [2,3] و[3,6]، اللتين تبدآن قبل 4، ويترك مجالًا لـ [5,7]: أي فترتان أبقيتهما. إزالة [1,4] وإبقاء [2,3] ثم [3,6] يُبقي أيضًا فترتين. لا يصل أي مسار إلى 3، لذا تزيل 4-2 = 2.
يمكن لكل فترة أن تضاعف عدد المسارات، لذا تؤدي n فترات إلى ما يصل إلى 2^n مسارًا. ثلاثون فترة غير متداخلة تعني بالفعل أكثر من مليار استدعاء، وتصل الاختبارات إلى 5000 فترة. كما أن الاستدعاء التعاودي يتعمق n مستوى: 5000 استدعاء في أكبر الاختبارات، متجاوزًا الحد الافتراضي في Python البالغ 1,000.
الخوارزمية
- رتّب الفترات حسب بداياتها، مع إبقاء كل بداية مرتبطة بنهايتها.
- عرّف
mostKept(i, last): أكبر عدد من الفترات التي يمكنك الاحتفاظ بها بدءًا من الموضعi، عندما يكونlastموضع أحدث فترة تم الاحتفاظ بها (-1في حال عدم وجود أي فترة). - إذا تجاوزت نهاية القائمة، فأعِد
0. وإلا، ابدأ منmostKept(i+1, last)، وهي نتيجة إزالة الفترةi. - إذا بدأت الفترة
iعند نهاية الفترةlastأو بعدها، فجرّب أيضًا1 + mostKept(i+1, i)واحتفظ بالنتيجة الأكبر. - أعِد
nناقصmostKept(0, -1).
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
def most_kept(i, last):
# The most intervals you can keep among i..n-1, when interval last
# is the latest one kept so far (-1: nothing kept yet).
if i == n:
return 0
best = most_kept(i + 1, last) # remove interval i
if last == -1 or intervals[i][0] >= intervals[last][1]:
best = max(best, 1 + most_kept(i + 1, i)) # keep interval i
return best
return n - most_kept(0, -1)أطول سلسلة باستخدام البرمجة الديناميكية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
يجيب البحث أعلاه عن السؤال نفسه مرارًا وتكرارًا: ما أطول سلسلة تنتهي بهذه الفترة؟ خزّن هذه الإجابة مرة واحدة لكل فترة. رتّب حسب نقطة البداية، ولتكن chain[i] أكبر عدد من الفترات التي يمكنك الاحتفاظ بها عندما تكون الفترة i هي الأخيرة التي احتفظت بها.
يجب أن تنتهي الفترة المحفوظة مباشرةً قبل i عند starts[i] أو قبله. وكل فترة من هذا النوع تأتي قبلها في الترتيب: فهي تبدأ قبل أن تنتهي، لذا تبدأ قبل starts[i]. وهذا يعطينا chain[i] = 1 + chain[j] لأفضل j سابق بحيث ends[j] ≤ starts[i]، أو 1 عندما لا تلائم أي فترة. أكبر قيمة في chain هي أكبر عدد يمكنك الاحتفاظ به.
في المثال الأول، بعد الترتيب كالتالي: [1,4]، [2,3]، [3,6]، [5,7]، تكون القيم 1 و1 و2 و2: يمكن أن تأتي [3,6] بعد [2,3]، ويمكن أن تأتي [5,7] بعد [1,4] أو [2,3]. أطول سلسلة طولها 2، لذا تحذف 4-2 = 2.
تنظر كل فترة إلى الوراء وتفحص كل فترة تسبقها، أي n(n-1)/2 عملية تحقق. عندما تكون n = 5000، يكون ذلك نحو 12.5 مليون عملية تحقق: وهذا مناسب للغات المُترجَمة، لكنه بطيء جدًا في اللغات الأبطأ عند أكبر حالات الاختبار، كما أنه أبطأ بكثير من النهج الجشع أدناه.
الخوارزمية
- رتّب الفترات حسب بداياتها، مع إبقاء كل بداية مرتبطة بنهايتها.
- عيّن
chain[i] = 1لكل فترة. - لكل
iولكلj < iبحيثends[j] ≤ starts[i]، عيّنchain[i]إلىchain[j]+1إذا كانت تلك القيمة أكبر. - أعِد
nمطروحًا منه أكبر قيمة فيchain.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(starts, ends)) # by start time
n = len(intervals)
# chain[i]: the most intervals you can keep when interval i is the last one kept
chain = [1] * n
for i in range(n):
for j in range(i):
if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
chain[i] = chain[j] + 1
return n - max(chain)الجشع: احتفظ بالفترة التي تنتهي أولًا
الفكرة
انظر إلى الفترة ذات أصغر نهاية. أي حل أمثل يحتفظ بها دائمًا. خذ أي مجموعة من الفترات بأكبر حجم يمكنك الاحتفاظ بها، واستبدل أقدم فترة فيها بهذه الفترة. تنتهي الفترة الجديدة في موعد لا يتجاوز موعد انتهاء الفترة التي استُبدلت بها، لذا تظل نهايتها عند بداية الفترة التالية المحتفَظ بها أو قبلها. تظل المجموعة خالية من التداخلات ويظل حجمها كما هو، لذا فإن الاحتفاظ بأقرب نهاية لا يكلّفك شيئًا.
بمجرد الاحتفاظ بها، تتداخل معها كل فترة تبدأ قبل نهايتها، ويجب حذفها. ما يتبقى هو السؤال نفسه على الفترات التي تبدأ عند تلك النهاية أو بعدها، لذا طبّق القاعدة نفسها مجددًا. عمليًا: رتّب حسب النهاية، ومرّ على القائمة، واحتفظ بقيمة lastEnd، وهي نهاية آخر فترة احتُفظ بها. احتفظ بأي فترة تبدأ عند lastEnd أو بعدها؛ واحسب أي فترة أخرى على أنها محذوفة.
المثال الأول بعد الترتيب حسب النهاية هو [2,3]، [1,4]، [3,6]، [5,7]. احتفظ بـ [2,3]، لذا lastEnd = 3. تبدأ [1,4] عند 1، قبل 3: احذفها. تبدأ [3,6] عند 3، وليس قبل 3: احتفظ بها، lastEnd = 6. تبدأ [5,7] عند 5، قبل 6: احذفها. فترتان محذوفتان.
تبدو مفاتيح أخرى مغرية لكنها لا تنجح. فالترتيب حسب البداية يُبقي على [0,100] مع أنها تشمل [1,2] و[3,4] و[5,6]، فيحذف ثلاث فترات بدلًا من واحدة. كما أن الاحتفاظ بأقصر فترة لا ينجح مع [1,5] و[4,7] و[6,10]: تتداخل الفترة القصيرة [4,7] مع الفترتين الأخريين، لذا فإن الاحتفاظ بها يؤدي إلى حذف فترتين بينما يكفي حذف واحدة. النهاية هي المفتاح الذي يترك أكبر مساحة ممكنة لكل ما يأتي بعدها.
تستغرق عملية الترتيب O(n log n)، ويستغرق المرور على القائمة O(n). وتشغل النسخة المرتبة من الفترات مساحة O(n).
الخوارزمية
- رتّب الفترات حسب نهايتها، مع إبقاء كل نهاية مرتبطة ببدايتها.
- احتفظ بالفترة الأولى: عيّن
lastEndإلى نهايتها وعيّنremovedإلى0. - لكل فترة تالية، إذا بدأت عند
lastEndأو بعده، فاحتفظ بها وعيّنlastEndإلى نهايتها. - وإلا، فأضف 1 إلى
removed. - أعِد
removed.
def eraseOverlapIntervals(starts, ends):
intervals = sorted(zip(ends, starts)) # by end time
removed = 0
last_end = intervals[0][0] # the interval that ends first is always kept
for end, start in intervals[1:]:
if start >= last_end:
last_end = end # it fits after the last kept interval: keep it
else:
removed += 1 # it overlaps the last kept interval: remove it
return removed
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من مفتاح الترتيب أو من المقارنة عند نقطة التلامس.
- اعتبار الفترات المتلامسة متداخلة. عند استخدام
start > lastEndبدلًا منstart ≥ lastEnd، تفقد السلسلة [1,2]، [2,4]، [4,6] الفترة [2,4]، التي تبدأ تمامًا عند نهاية [1,2]، وتكون الإجابة 1 بدلًا من 0. - الترتيب حسب نقطة البداية والاحتفاظ دائمًا بالفترة الأسبق عند التداخل. فترة واسعة مثل [0,100] تُقصي بعد ذلك [1,2] و[3,4] و[5,6]. إذا رتبت حسب نقطة البداية، فاحتفظ بالفترة التي تنتهي أولًا من الفترتين المتداخلتين.
- مقارنة كل فترة بالفترة المجاورة لها في القائمة المرتبة بدلًا من آخر فترة تم الاحتفاظ بها. بعد إزالة [1,4]، يجب فحص الفترة التالية مقارنةً بنهاية [2,3]، لا مقارنةً بـ 4.
- ترتيب
startsوendsكقائمتين منفصلتين. يجب أن تبقى كل نهاية مرتبطة بنقطة بدايتها، وإلا فستقارن نقطة بداية بنهاية فترة أخرى. - إرجاع عدد الفترات التي تحتفظ بها. السؤال يطلب عدد الفترات التي أُزيلت، وهو
nناقص ذلك العدد.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة الفترات غير المتداخلة؟
يرتّب الحل الجشع الفترات حسب نهايتها في O(n log n)، ثم يمرّ عليها مرة واحدة في O(n)، لذا يكون التعقيد الإجمالي O(n log n). وتستهلك النسخة المرتّبة من الفترات مساحة O(n). أمّا نسخة البرمجة الديناميكية فتعقيدها O(n²)، وتجربة كل مجموعة للاحتفاظ بها تعقيدها O(2^n).
لماذا يؤدي الترتيب حسب وقت الانتهاء إلى أقل عدد من عمليات الإزالة؟
يمكن للفترة التي تنتهي أولًا أن تحل محل الفترة الأولى في أي حل أمثل من دون أن تُنشئ تداخلًا، لأنها لا تنتهي بعدها. لذا يوجد حل أمثل يحتفظ بها، وبعد إزالة كل ما يتداخل معها، تصبح المسألة المتبقية هي المسألة نفسها على مجموعة أصغر. ويُظهر تكرار هذه الحجة أن كل اختيار جشع آمن.
هل يمكنك الترتيب حسب وقت البدء بدلًا من ذلك؟
نعم، مع قاعدة مختلفة للتداخل. مرّ على الفترات حسب بدايتها، وعندما تتداخل الفترة التالية مع آخر فترة احتفظت بها، احتسب عملية إزالة واحدة واحتفظ بالفترة التي تنتهي أولًا. يزيل العدد نفسه من الفترات مثل الفرز حسب النهاية، ويعمل في الوقت نفسه O(n log n).
هل مسألة الفترات غير المتداخلة هي نفسها مسألة اختيار الأنشطة؟
إنه الجانب الآخر منها. يطلب اختيار الأنشطة أكبر عدد من الفترات التي لا تتداخل؛ أما هذه المسألة فتطلب إزالة أقل عدد ممكن، وهو n ناقص ذلك العدد. تحل القاعدة الجشعة نفسها، وهي الاحتفاظ بالنشاط الذي ينتهي أولًا، المسألتين كلتيهما.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def eraseOverlapIntervals(starts, ends):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
المتوقع
2