Merge Intervals

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

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

اكتب دالة باسم mergeIntervals تأخذ مصفوفتين من الأعداد الصحيحة، starts وends، وتُرجع الفترات المدمجة.

تُمرَّر الفترات على هيئة مصفوفتين لأن بعض اللغات هنا لا تقبل مصفوفة ثنائية الأبعاد كمدخل: الفترة i هي [starts[i], ends[i]]، وللمصفوفتين الطول نفسه. الفترات غير مرتبة.

ادمج كل مجموعة من الفترات المتداخلة. وتُعد الفترات التي تتلامس عند أحد الطرفين متداخلة أيضًا. أعد الفترات المدمجة كمصفوفة ثنائية الأبعاد [[start, end], ...]، مرتبة حسب نقطة البداية.

على سبيل المثال، starts = [5, 1, 12, 3] وends = [7, 4, 14, 6] تصف الفترات [5, 7] و[1, 4] و[12, 14] و[3, 6]، التي تندمج لتصبح [[1, 7], [12, 14]].

القيود: 1 <= starts.length == ends.length <= 10^4، و0 <= starts[i] <= ends[i] <= 10^4.