Merge Intervals
تحصل على مجموعة من الفواصل، كلٌّ منها نطاق من الأعداد الصحيحة يبدأ من قيمة وينتهي عند أخرى. ادمج كل مجموعة من الفواصل المتداخلة في فاصل واحد يغطي المجموعة بأكملها، وأعِد الفواصل المدمجة مرتبةً حسب نقطة البداية. تُعد الفواصل التي تتلامس فقط، مثل [1, 4] و[4, 5]، متداخلة.
تأتي الفواصل في مصفوفتين لهما الطول نفسه: الفاصل i هو [starts[i], ends[i]]. أعد مصفوفة ثنائية الأبعاد، وهي قائمة من أزواج [start, end].
الدالة
- startsinteger-array
- بداية كل فترة
- endsinteger-array
- نهاية كل فترة زمنية، عند الفهرس نفسه الذي تبدأ عنده
- تُرجعinteger-2d-array
- الفترات المدمجة على هيئة أزواج [start, end]، مرتبة حسب نقطة البداية
القيود
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- تصل الفترات بأي ترتيب.
- تُعَدّ الفترات التي تتلامس عند أحد طرفيها فقط متداخلة.
أمثلة
- المدخلات
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- المخرجات
- [[1, 7], [12, 14]]
- الشرح
- حسب ترتيب البداية، تتداخل [1, 4] مع [3, 6]، التي تتداخل مع [5, 7]، لذا تصبح الفترات الثلاث [1, 7]. تبدأ [12, 14] بعد 7 وتبقى منفردة.
- المدخلات
- starts = [6, 1]ends = [9, 6]
- المخرجات
- [[1, 9]]
- الشرح
- الفترتان هما [6, 9] و[1, 6]. وهما تشتركان في النقطة 6، وبما أن التلامس يُعد تداخلًا، فهما تندمجان لتصبحا [1, 9].
سؤال إضافي
تصل الفترات مدمجة بالفعل ومرتبة حسب نقطة البداية، وعليك إضافة فترة جديدة. هل يمكنك إرجاع القائمة المدمجة بزمن O(n)، من دون إعادة الفرز؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
طابِق أولًا كل بداية بنهايتها، حتى تعمل مع فترات كاملة بدلًا من مصفوفتين منفصلتين.
رتّب الفترات حسب نقطة البداية. بعد ذلك، لا يمكن لفترة أن تتداخل إلا مع المجموعة التي تسبقها مباشرةً، وليس مع مجموعة أسبق منها.
تجوّل بين الفترات المرتبة مع الاحتفاظ بآخر فترة مدمجة. إذا كانت بداية الفترة التالية أقل من نهايتها أو تساويها، فاجعل نهايتها تساوي الأكبر من النهايتين. وإلا، تكون تلك المجموعة قد اكتملت وتبدأ الفترة التالية مجموعةً جديدة.
الحل
يتطلب دمج الأزواج بأي ترتيب إجراء تمريرات متكررة، لأن كل عملية دمج توسّع فترة وتتيح لها الوصول إلى فترات سبق أن تحققت منها. رتّب حسب نقطة البداية بدلًا من ذلك. عندها لا يمكن للفترة أن تتداخل إلا مع المجموعة التي تنشئها، وتكفي تمريرة واحدة لإنجاز المهمة.
ادمج الأزواج المتداخلة حتى لا يتغير شيء
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
تتداخل الفترتان [a, b] و[c, d] عندما يكون c ≤ b وa ≤ d، وتغطيهما كلتاهما [min(a, c), max(b, d)]. يزيل كل دمج فترةً واحدة، لذا تتوقف العملية، وبمجرد أن تمر جولة كاملة من دون العثور على أي تداخل، لا تشترك أي فترتين متبقيتين في نقطة. لا تكفي جولة واحدة: فالفترة الناتجة عن الدمج أوسع، وقد تمتد الآن لتصل إلى فترة سبق أن قورنت بجزئها الأصغر في أثناء الجولة.
تقارن الجولة الواحدة نحو n²/2 زوجًا، وقد تحتاج إلى ما يصل إلى n جولات: O(n³). فالجولة الواحدة على 10^4 فترة تتطلب بالفعل 5 × 10^7 مقارنة.
الخوارزمية
- انسخ
startsوends، واحتفظ بعددnللفترات الحية. - قارن كل فترة
iبكل فترة لاحقةj. إذا تداخلتا، فمدّدiلتغطيj، وانقل آخر فترة حية إلى الخانةj، وخفّضnبمقدار واحد. - بعد الدمج، تحقّق من الخانة
jمرة أخرى، إذ توجد فيها الآن فترة مختلفة. - كرّر المرور حتى يمرّ أحدها دون إجراء أي دمج.
- اقرن كل بداية حية بنهايتها، ورتّب الأزواج حسب البداية، ثم أعدها.
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))رتّب حسب نقطة البداية وامسح مرة واحدة
الفكرة
بعد الترتيب حسب نقطة البداية، تبدأ الفترة التالية في موضع لا يسبق أي شيء في المجموعة الأخيرة، التي تنتهي عند e. إذا كانت نقطة بدايتها أقل من أو تساوي e، فهي تتداخل مع المجموعة أو تلامسها وتنضم إليها، وتصبح e الأكبر بين نقطتي النهاية. إذا كانت نقطة بدايتها بعد e، فلن تتمكن أي فترة لاحقة من الرجوع إلى المجموعة أيضًا، لأن الفترات اللاحقة تبدأ في مواضع أبعد إلى اليمين. تنتهي المجموعة، وتبدأ الفترة مجموعة جديدة.
يستغرق الترتيب O(n log n)، وتمر عملية المسح على كل فترة مرة واحدة. تُغلق المجموعات من اليسار إلى اليمين، لذا تكون النتيجة مرتبة حسب نقطة البداية.
الخوارزمية
- اربط كل بداية بنهايتها: الفاصل
iهو[starts[i], ends[i]]. - رتّب الأزواج حسب البداية.
- مرّ على الأزواج المرتّبة. إذا كانت النتيجة فارغة، أو كانت بداية الزوج بعد نهاية آخر فاصل مدمج، فأضف الزوج بوصفه فاصلًا جديدًا.
- وإلا، فعيّن نهاية آخر فاصل مدمج لتكون الأكبر بين نهايته ونهاية الزوج.
- أعِد القائمة المدمجة.
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
أخطاء شائعة وحالات حدّية
- المقارنة باستخدام
<بدلًا من≤. يجب دمج الفترات المتلامسة مثل[1, 4]و[4, 5]. - تعيين النهاية إلى نهاية الفترة الجديدة بدلًا من الأكبر بين النهايتين. يجب أن تبقى
[1, 10]كما هي عند إتباعها بـ[2, 3]. - ترتيب
startsوحدها ثم قراءةendsعند المواضع الجديدة، بحيث يُقرن أحد أوقات البدء بنهاية فترة أخرى. أقرنها أولًا، أو رتّب الفهارس. - المقارنة مع فترة الإدخال السابقة بدلًا من آخر فترة مدمجة. في
[1, 10]،[2, 3]،[4, 5]، تقع الفترة الثالثة داخل[1, 10]رغم أنها لا تتلامس مع[2, 3]. - في C، عدم تعيين
*returnSizeإلى عدد الفترات المدمجة، وتعيين حجم كل عمود إلى 2.
أسئلة شائعة3
ما هو التعقيد الزمني لدمج الفترات؟
يعمل حلّ الفرز والمسح في زمن O(n log n) لعدد n من الفترات: تبلغ كلفة الفرز O(n log n)، والمسح O(n). ويستخدم مساحة إضافية قدرها O(n) للأزواج المرتبة والنتيجة.
لماذا نرتب الفترات حسب نقطة البداية وليس حسب نقطة النهاية؟
[5, 6] قبل [1, 10]، وسيُبقي المسح من الأمام على 5 كنقطة بداية على نحو خاطئ.هل يمكنك دمج الفترات دون استخدام مساحة إضافية؟
نعم، إذا كان بإمكانك تغيير المُدخل. رتّب الفترات في مكانها، ثم اكتب كل فترة مدمجة فوق مقدمة المصفوفة نفسها، واحتفظ بمؤشر آخر فترة كتبتها. يظل الزمن O(n log n)، والمساحة الإضافية الوحيدة هي ما تستخدمه عملية الترتيب في لغتك.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def mergeIntervals(starts, ends):
# اكتب الكود هنااختبار #1
اختبار #2
الوسائط
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
الإخراج المتوقع
[[1, 7], [12, 14]]