Merge Intervals

متوسط
توضیحات

مسئله

با دریافت یک آرایه از بازه‌ها (intervals) به شکل [start, end]، تمام بازه‌های هم‌پوشان را با یکدیگر ادغام کنید و در نهایت، فهرستی مرتب‌شده از بازه‌های غیرهم‌پوشان را برگردانید؛ به‌طوری‌که تمام محدوده‌های ورودی را پوشش دهد.

قوانینی که باید در صورت مسئله ذکر شوند

1. بازه‌هایی که نقاط انتهایی مشترک دارند نیز هم‌پوشان محسوب می‌شوند و باید ادغام شوند:

برای مثال، دو بازه [1,4] و [4,5] باید به [1,5] تبدیل شوند.

این مورد رایج‌ترین دلیل اختلاف در پیاده‌سازی‌های مختلف این مسئله است.

2. بازه‌های ورودی لزوماً مرتب‌شده نیستند:

بنابراین، خروجی باید بر اساس مقدار start به‌صورت صعودی مرتب شده باشد.

3. اگر یک بازه به‌طور کامل درون بازه دیگری قرار داشته باشد، در آن ادغام می‌شود:

برای مثال، بازه [2,3] که درون [1,10] قرار دارد، در نهایت به [1,10] تبدیل می‌شود.

4. تمام بازه‌ها باید شرط زیر را داشته باشند:

start <= end

محدودیت‌ها (Constraints)

  • 1 <= len(intervals) <= 10^4
  • 0 <= start <= end <= 10^5
نمونه تست‌کیس‌ها
ورودی (Input)
[[1,3],[2,6],[8,10],[15,18]]
خروجی (Output)
[[1,6],[8,10],[15,18]]
ورودی (Input)
[[5,6],[1,4]]
خروجی (Output)
[[1,4],[5,6]]
ورودی (Input)
[[1,10],[2,3],[4,5]]
خروجی (Output)
[[1,10]]

شروع چالش

برای دسترسی به محیط کدنویسی آنلاین و ارسال راه‌حل، ثبت‌نام کنید.

ثبت‌نام و شروع

قبلاً ثبت‌نام کرده‌اید؟ وارد شوید

آمار و محدودیت‌ها

۲۰ XP
پاداش
۲s
زمان مجاز
۲۵۰ MB
حافظه مجاز
۱
شروع
۱
حل شده

زبان‌های مجاز

python