Insert Interval

Q: ما هو التعقيد الزمني لإدراج فترة زمنية؟

يعمل الحل ذو المرور الواحد في زمن O(n) : يُنسخ كل فاصل أو يُدمج مرة واحدة بالضبط. تحتوي النتيجة على ما يصل إلى n+1 من الفواصل، لذا تتطلب مساحة O(n) ، ولا يزداد حجم أي شيء آخر مع حجم المُدخلات. تستغرق إضافة الفاصل وإعادة الترتيب O(n log n) بدلًا من ذلك.

Q: ما الفرق بين إدراج فاصل زمني ودمج الفواصل الزمنية؟

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

Q: كيف تتحقق مما إذا كان هناك تداخل بين فترتين؟

يتشارك الفترتان [a, b] و [c, d] نقطةً واحدةً على الأقل بالضبط عندما يكون a ≤ d و c ≤ b . وهذا يعني احتساب الفترات المتلامسة مثل [2, 4] و [4, 8] على أنها متداخلة، وهذا ما تريده هذه المسألة. إذا كان يجب أن تبقى الفترات المتلامسة منفصلة، فستستخدم a < d و c < b بدلًا من ذلك.

Q: هل يمكن للبحث الثنائي أن يجعل إدراج الفاصل الزمني أسرع؟

يحدّد البحث الثنائي موضعي بداية المدى المدمج ونهايته في O(log n) ، لأن البدايات والنهايات مرتبة. لكن الدالة تظل تُرجع قائمة جديدة، ونسخ الفترات التي لم تتغير إليها يتطلب O(n) . لذا يبقى الإجمالي O(n) . يكون البحث الثنائي مفيدًا عندما تكون الفترات مخزنة في بنية بيانات يمكنها حذف مدى وإدراجه دون نسخ، مثل شجرة متوازنة.

متوسطالفترات

+10

تحصل على قائمة من الفترات مرتبة حسب نقطة البداية، معطاة على شكل مصفوفتين لهما الطول نفسه: الفترة i هي [starts[i], ends[i]]. لا تتداخل أي فترتين منها ولا تتلامسان. وتحصل أيضًا على فترة جديدة واحدة، [newStart, newEnd]. أدرجها، وادمجها مع كل فترة تتداخل معها أو تلامسها، ثم أعد جميع الفترات في صورة مصفوفة ثنائية الأبعاد من أزواج [start, end]، مرتبة حسب نقطة البداية.

تتلامس فترتان عندما تنتهي إحداهما عند نقطة بداية الأخرى، كما في [2, 4] و[4, 8]، وتُدمج الفترات المتلامسة في فترة واحدة. أما [1, 2] و[3, 4] فلا تشتركان في أي نقطة، لذا تبقيان منفصلتين.

الدالة

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: بداية كل فترة، بترتيب تصاعدي
endsinteger-array: نهاية كل فترة، والبدايات المطابقة
newStartinteger: بداية الفترة المراد إدراجها
newEndinteger: نهاية الفاصل الزمني المراد إدراجه
تُرجعinteger-2d-array: الفترات بعد الإدراج على شكل أزواج [start, end]، مرتبة حسب start

القيود

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: الفترات مرتبة حسب وقت البدء، ولا تتداخل أي فترتين منها أو تتلامسان.
0 ≤ newStart ≤ newEnd ≤ 10⁵

أمثلة

المدخلات: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
المخرجات: [[1, 3], [5, 12], [15, 18]]
الشرح: [6, 11] يتداخل مع [5, 7] و[10, 12]، لذا تصبح الفترات الثلاث [5, 12]. ينتهي [1, 3] قبل 6 ويبدأ [15, 18] بعد 12، لذا يبقيان كما هما.

المدخلات: starts = [2, 8]ends = [4, 9]newStart = 4newEnd = 8
المخرجات: [[2, 9]]
الشرح: [4, 8] يلامس [2, 4] عند 4 و[8, 9] عند 8. يُعَدّ التلامس تداخلًا، لذا تندمج الفترات الثلاث في [2, 9].

المدخلات: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
المخرجات: [[1, 2], [5, 6], [9, 10]]
الشرح: تقع [5, 6] في الفجوة بين 2 و9 ولا تلامس أيًّا من الفترتين المجاورتين، لذا تُدرج بينهما ولا يندمج أي شيء.

+20 اختبارات مخفية عند الإرسال

سؤال إضافي

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

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

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

أضِفه وادمج كل شيء مجددًا

الفكرة

إذا كنت قد حللت مسألة دمج الفترات، فيمكنك إعادة استخدامها هنا. أضف الفترة الجديدة إلى القائمة، ورتّب جميع الفترات البالغ عددها n+1 حسب البداية، ثم ادمجها. بعد الترتيب، لا يمكن للفترة أن تتداخل إلا مع المجموعة التي تسبقها مباشرة، لذا تجتاز القائمة مع الاحتفاظ بآخر فترة مدمجة. عندما تكون البداية التالية عند نهاية الفترة الحالية أو قبلها، مدّد النهاية. وإلا فهناك فجوة فعلية، وتبدأ فترة جديدة.

طبّق ذلك على المثال الأول. تصبح القائمة [1, 3]، [5, 7]، [6, 11]، [10, 12]، [15, 18]. تبقى [1, 3] منفردة، لأن 5 أكبر من 3. و6 لا تتجاوز 7، لذا تمتد [5, 7] إلى [5, 11]. و10 لا تتجاوز 11، لذا تمتد إلى [5, 12]. أما 15 فهي أكبر من 12، لذا تبدأ [15, 18] فترة جديدة.

هذا صحيح، وعند وجود 2000 فترة يعمل بسرعة. لكنه يتجاهل حقيقتين أُعطيتا لك: القائمة مرتبة بالفعل، والفترات القديمة لا تندمج بعضها مع بعض مطلقًا. إن دفع كلفة O(n log n) لإعادة ترتيب قائمة لا يوجد فيها إلا موضع واحد خارج الترتيب هو الخطوة التي سيطلب منك المحاور حذفها.

الخوارزمية

اربط كل بداية بنهايتها، وأضف [newStart, newEnd] إلى القائمة.
رتّب الفواصل الزمنية حسب البداية.
مرّ عليها بالترتيب، مع الاحتفاظ بآخر فاصل زمني مدمج.
إذا كانت البداية التالية أقل من النهاية المحفوظة أو مساوية لها، فاجعل النهاية المحفوظة أكبر النهايتين.
وإلا، فأضف الفاصل الزمني التالي بوصفه فاصلًا مدمجًا جديدًا. أَعِد القائمة المدمجة.

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

مرور واحد في ثلاثة أجزاء

الفكرة

مرّ على القائمة مرة واحدة باستخدام الفهرس i وقسّمها إلى ثلاثة أجزاء. أولًا، كل فترة تحقق ends[i] < newStart تنتهي قبل بداية الفترة الجديدة، لذلك لا تشترك معها في أي نقطة: انسخها إلى النتيجة. الاختبار هنا هو < الصارم لأن الفترة التي تنتهي تمامًا عند newStart تلامس الفترة الجديدة ويجب دمجها معها.

ثانيًا، كل فترة تحقق starts[i] ≤ mergedEnd تتداخل مع الفترة التي تنشئها أو تلامسها. ادمجها فيها: تصبح mergedStart أصغر بداية، وmergedEnd أكبر نهاية. تقع الفترات في هذا الجزء متجاورةً لأن القائمة مرتبة. بمجرد أن تبدأ فترة بعد mergedEnd، تبدأ كل فترة لاحقة إلى يمينها أكثر، لذا لا يمكن دمج أي فترة بعدها. أضف الفترة المدمجة؛ وتشمل هذه الخطوة أيضًا حالة خلو هذا الجزء من الفترات، فتُضاف الفترة الجديدة وحدها.

ثالثًا، انسخ كل ما تبقّى. تبدأ هذه الفترات بعد نهاية الفترة المدمجة، وهي متباعدة عن بعضها أصلًا.

تتبّع المثال الأول. تنتهي [1, 3] قبل 6: انسخها. تبدأ [5, 7] عند 5، وهو أقل من أو يساوي 11: تصبح الفترة المدمجة [5, 11]. تبدأ [10, 12] عند 10، وهو أقل من أو يساوي 11: فتصبح [5, 12]. تبدأ [15, 18] بعد 12، لذا أضف [5, 12] وانسخ [15, 18]. يُنظر إلى كل فترة مرة واحدة، لذا يكون الزمن O(n)، والذاكرة الإضافية الوحيدة هي النتيجة نفسها.

الخوارزمية

انسخ الفواصل إلى النتيجة ما دام ends[i] < newStart.
عيّن mergedStart = newStart وmergedEnd = newEnd.
ما دام starts[i] ≤ mergedEnd، عيّن mergedStart إلى بداية أصغر وmergedEnd إلى نهاية أكبر، ثم انتقل إلى التالي.
أضف [mergedStart, mergedEnd].
انسخ الفواصل المتبقية وأعِد النتيجة.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

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

الحلقة قصيرة، لذا تأتي معظم الأخطاء من مقارنة واحدة خاطئة أو من نسيان حالة عند أحد طرفي القائمة.

استخدام متباينة غير صحيحة للفترات المتلامسة. عند استخدام ends[i] ≤ newStart في الحلقة الأولى، أو starts[i] < mergedEnd في الحلقة الثانية، تبقى [2, 4] و[4, 8] منفصلتين. تُدمج الفترات المتلامسة، لذا يكون الاختبار الأول صارمًا والثاني غير صارم.
دمج الفترات التي تبدو متجاورة فقط. لا تشترك [1, 2] و[3, 4] في أي نقطة، لذا فإن المقارنة مع mergedEnd + 1 تدمج فترات ينبغي أن تبقى منفصلة.
الإبقاء على newStart كبداية الفترة المدمجة. عندما تبدأ الفترة الجديدة داخل فترة قديمة، كما في [6, 11] داخل [5, 7]، تبدأ النتيجة عند 5. اختر الأصغر من البدايتين.
إضافة الفترة الجديدة فقط عندما تتداخل مع فترة أخرى. عندما تأتي قبل كل الفترات أو بعدها أو في فجوة بينها، لا تعمل الحلقة الوسطى مطلقًا، ومع ذلك يجب إضافة الفترة الجديدة.
قراءة starts[i] أو ends[i] قبل التحقق من i < n. عندما تمتد الفترة الجديدة إلى ما بعد آخر فترة، يتجاوز الفهرس نهاية المصفوفات.

أسئلة شائعة4

ما هو التعقيد الزمني لإدراج فترة زمنية؟

يعمل الحل ذو المرور الواحد في زمن O(n): يُنسخ كل فاصل أو يُدمج مرة واحدة بالضبط. تحتوي النتيجة على ما يصل إلى n+1 من الفواصل، لذا تتطلب مساحة O(n)، ولا يزداد حجم أي شيء آخر مع حجم المُدخلات. تستغرق إضافة الفاصل وإعادة الترتيب O(n log n) بدلًا من ذلك.

ما الفرق بين إدراج فاصل زمني ودمج الفواصل الزمنية؟

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

كيف تتحقق مما إذا كان هناك تداخل بين فترتين؟

يتشارك الفترتان [a, b] و[c, d] نقطةً واحدةً على الأقل بالضبط عندما يكون a ≤ d وc ≤ b. وهذا يعني احتساب الفترات المتلامسة مثل [2, 4] و[4, 8] على أنها متداخلة، وهذا ما تريده هذه المسألة. إذا كان يجب أن تبقى الفترات المتلامسة منفصلة، فستستخدم a < d وc < b بدلًا من ذلك.

هل يمكن للبحث الثنائي أن يجعل إدراج الفاصل الزمني أسرع؟

يحدّد البحث الثنائي موضعي بداية المدى المدمج ونهايته في O(log n)، لأن البدايات والنهايات مرتبة. لكن الدالة تظل تُرجع قائمة جديدة، ونسخ الفترات التي لم تتغير إليها يتطلب O(n). لذا يبقى الإجمالي O(n). يكون البحث الثنائي مفيدًا عندما تكون الفترات مخزنة في بنية بيانات يمكنها حذف مدى وإدراجه دون نسخ، مثل شجرة متوازنة.

Python

def insertInterval(starts, ends, newStart, newEnd):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

المتوقع

[[1, 3], [5, 12], [15, 18]]