Insert Interval

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

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

Q: ما الفرق بين Insert Interval وMerge Intervals؟

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

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

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

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

+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 ولا تلامس أيًّا من الجارين، لذا تُدرج بينهما ولا يندمج أيٌّ منها.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

أضِفه وادمج كل شيء مرة أخرى

الفكرة

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

تكلّف عملية الترتيب 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

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

الفكرة

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

داخل المقطع، تتداخل الفترة التي تحقق starts[i] ≤ mergedEnd مع الفترة التي تنشئها أو تلامسها، لذا فهي توسّعها إلى البداية الأصغر والنهاية الأكبر. أول فترة تبدأ بعد mergedEnd تنهي المقطع، لأن كل فترة تليها تبدأ إلى اليمين أكثر. عندما يكون المقطع فارغًا، تُدرج الفترة الجديدة وحدها. في المثال الأول، تُنسخ [1, 3]، وتوسّع [5, 7] و[10, 12] الفترة [6, 11] لتصبح [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] منفصلتين. الاختبار الأول صارم، والثاني غير صارم.
المقارنة مع mergedEnd + 1. هذا يدمج [1, 2] و[3, 4]، مع أنهما لا تشتركان في أي نقطة.
الإبقاء على newStart كبداية للفترة المدمجة. تبدأ [6, 11] داخل [5, 7]، لذا تبدأ النتيجة عند 5.
إضافة الفترة الجديدة فقط عندما تتداخل مع فترة أخرى. عندما تقع في فجوة أو تتجاوز أحد الطرفين، كما في [5, 6]، لا تُنفَّذ الحلقة الوسطى، ومع ذلك يجب إضافتها.
قراءة starts[i] قبل التحقق من i < n. إذا امتدت فترة جديدة إلى ما بعد الأخيرة، فسيخرج الفهرس عن الحدود.

أسئلة شائعة3

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

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

ما الفرق بين Insert Interval وMerge Intervals؟

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

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

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

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]]