Non-overlapping Intervals
يمتد الفاصل i من starts[i] إلى ends[i]. أعد أقل عدد من الفواصل التي يجب إزالتها بحيث لا يتداخل أي فاصلين من الفواصل المتبقية. الفاصلان اللذان يتلامسان فقط، حيث ينتهي أحدهما عند النقطة نفسها التي يبدأ عندها الآخر، لا يتداخلان.
الدالة
- 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.
سؤال إضافي
افترض أن لكل فترة قيمة، وأنك تريد أكبر مجموع للقيم بين الفترات التي لا تتداخل. هل يظل اختيار الفترة التي تنتهي أولًا ناجحًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
بدلًا من اختيار ما تريد إزالته، فكّر فيما تريد الإبقاء عليه. ما علاقة أكبر مجموعة من الفترات الزمنية التي يمكنك الإبقاء عليها بالإجابة؟
من بين جميع الفترات، تترك الفترة التي تنتهي أولًا أكبر مساحة للبقية. ويحتفظ بها دائمًا أحد أفضل الحلول.
رتّب الفترات حسب نهايتها، وامشِ عليها مع تذكّر نهاية آخر فترة أبقيتها. أبقِ على الفترة التي تبدأ عند تلك النهاية أو بعدها؛ وتُحتسب كل فترة أخرى محذوفة.
الحل
إزالة أقل عدد من الفترات تعادل الاحتفاظ بأكبر عدد من الفترات غير المتداخلة: الإجابة هي n مطروحًا منه ذلك العدد. وتجد قاعدة جشعة واحدة هذا العدد في O(n log n): من بين الفترات التي لا تزال ملائمة، احتفظ دائمًا بالفترة التي تنتهي أولًا.
احتفِظ بكل فترة أو أزِلها
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
رتّب الفترات حسب نقطة البداية، وقرّر لكل فترة ما إذا كنت ستحتفظ بها أم تزيلها. يمكنك الاحتفاظ بها فقط إذا بدأت عند نهاية آخر فترة احتفظت بها أو بعدها، وبذلك تشكّل الفترات المحتفَظ بها سلسلة بلا تداخل. جرّب الخيارين عند كل فترة، وخذ العدد الأكبر؛ الإجابة هي n مطروحًا منه هذا العدد.
يمكن لكل فترة أن تضاعف عدد التفرعات، لذا تؤدي n فترة إلى ما يصل إلى 2^n مسارًا. حتى ثلاثون فترة غير متداخلة تعني بالفعل أكثر من مليار استدعاء، بينما تصل قيمة n إلى 5000.
الخوارزمية
- رتّب الفترات حسب نقطة البداية، مع إبقاء كل نقطة بداية مرتبطة بنقطة النهاية الخاصة بها.
- عرّف
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] أو قبله، لذا تبدأ قبلها وتأتي قبلها في الترتيب. وهذا يعطينا chain[i] = 1 + chain[j] لأفضل j من هذه الفترات، أو 1 إذا لم تلائم أيٌّ منها. في المثال الأول، القيم هي 1 و1 و2 و2، لذا تحتفظ بفترتين وتحذف فترتين.
تُجري الحلقة المزدوجة n(n-1)/2 من عمليات التحقق: نحو 12.5 مليونًا عندما تكون n = 5000.
الخوارزمية
- رتّب الفترات حسب بدايتها، مع إبقاء كل بداية مرتبطة بنهايتها.
- عيّن
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)النهج الجشع: احتفظ بالفترة التي تنتهي أولًا
الفكرة
خذ الفترة ذات النهاية الأصغر. تتضمن بعض الحلول المثلى هذه الفترة: في أي مجموعة أكبر حجمًا يمكنك الاحتفاظ بها، استبدل أبكر فترة بهذه الفترة. فهي تنتهي في وقت لا يتجاوز وقت انتهاء تلك الفترة، لذا تظل نهايتها عند بداية الفترة التالية المحتفَظ بها أو قبلها، ويبقى حجم المجموعة كما هو من دون تداخل. كل فترة تبدأ قبل نهايتها تتداخل معها ويجب حذفها، وما يتبقى هو المشكلة نفسها على الفترات التي تبدأ عند تلك النهاية أو بعدها.
في المثال الأول، بعد الترتيب حسب النهاية، تحتفظ بـ [2,3]، وتحذف [1,4]، وتحتفظ بـ [3,6]، وتحذف [5,7]. أما الاحتفاظ بالفترة الأقصر بدلًا من ذلك فيفشل مع [1,5]، [4,7]، [6,10]: إذ تتداخل [4,7] مع الفترتين الأخريين، ما يكلّف حذف فترتين بينما يكفي حذف واحدة.
تستغرق عملية الترتيب O(n log 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] الناتج 1 بدلًا من 0. - الترتيب حسب البداية والإبقاء على الفترة الأسبق عند التداخل. الفترة الواسعة [0,100] تُزيح بعدها الفترات [1,2] و[3,4] و[5,6]: ثلاث عمليات إزالة بدلًا من واحدة.
- مقارنة كل فترة بالفترة المجاورة لها في القائمة المرتبة بدلًا من آخر فترة تم الإبقاء عليها. في المثال الأول، يجب مقارنة [3,6] بنهاية [2,3]، وليس بنهاية الفترة المحذوفة [1,4]، وإلا فستكون الإجابة 3.
- ترتيب
startsوendsكقائمتين منفصلتين. يجب أن تبقى كل نهاية مرتبطة ببدايتها. - إرجاع عدد الفترات التي أبقيت عليها بدلًا من عدد الفترات التي أزلتها.
أسئلة شائعة3
ما هو التعقيد الزمني للفترات غير المتداخلة؟
يرتّب الحل الجشع حسب وقت الانتهاء في O(n log n) ويمرّ على الفترات مرة واحدة، لذا يكون الإجمالي O(n log n) مع استخدام مساحة O(n) للنسخة المرتّبة. أما إصدار البرمجة الديناميكية فتعقيده O(n²)، وتجربة كل مجموعة للاحتفاظ بها تعقيدها O(2^n).
هل يمكنك الترتيب حسب وقت البدء بدلًا من ذلك؟
نعم، مع قاعدة مختلفة عند التداخل. مرّ على الفترات بحسب بداياتها، وعندما تتداخل الفترة التالية مع آخر فترة احتفظت بها، فاحتسب حذفًا واحدًا واحتفظ بالفترة التي تنتهي أولًا من الاثنتين. يعطي ذلك العدد نفسه في الزمن نفسه O(n log n).
هل مسألة الفترات غير المتداخلة هي نفسها مسألة اختيار الأنشطة؟
هذا هو الوجه الآخر للمسألة. يطلب اختيار الأنشطة تحديد أكبر عدد من الفترات الزمنية غير المتداخلة؛ أما هذه المسألة فتطلب إزالة أقل عدد ممكن، وهو n ناقص ذلك العدد. تحل القاعدة الجشعة نفسها المسألتين: الاحتفاظ بالنشاط الذي ينتهي أولًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def eraseOverlapIntervals(starts, ends):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
starts = [3, 1, 5, 2] ends = [6, 4, 7, 3]
الإخراج المتوقع
2