ادغام فواصل (Merge Intervals)
الگوی ادغام فواصل: مرتب‌سازی بر اساس شروع + ادغام همپوشان‌ها؛ تقاطع، درج و پوشش فواصل
مسئله فواصل
مسائل فاصله (Interval) همه‌جا هستند: جلسات تقویم، رزرو اتاق، بازه‌های زمانی سرور، پوشش شبکه. الگوی حل همه یکی است!
الگوی سه‌گامی
- مرتب‌سازی بر اساس شروع فاصله — قلب الگو
- پیمایش: فاصله فعلی با آخرین فاصله ادغام‌شده مقایسه کن
- ادغام یا افزودن: اگر شروع فعلی ≤ پایان قبلی ← همپوشان ← ادغام (پایان = max)؛ وگرنه فاصله جدید
شرط همپوشانی
فاصله‌های (a_start, a_end) و (b_start, b_end):
همپوشان ⟺ a_start ≤ b_end و b_start ≤ a_endبعد از مرتب‌سازی بر اساس شروع، فقط یک شرط می‌ماند: شروع_فعلی ≤ پایان_آخرین
مسائل کلاسیک
| مسئله | تغییر الگو |
|---|---|
| ادغام فواصل همپوشان | الگوی پایه |
| درج فاصله در لیست مرتب | ادغام از محل درج |
| تقاطع دو لیست فاصله | max شروع‌ها، min پایان‌ها |
| اتاق‌های جلسات (حداقل چند اتاق؟) | رویدادهای شروع/پایان + شمارنده |
| می‌توان همه جلسات را شرکت کرد؟ | مرتب‌سازی + بررسی همپوشانی |
مثال گام‌به‌گام
ورودی: [(1,3), (2,6), (8,10), (15,18)]
مرتب (هست): شروع = 1, 2, 8, 15
(1,3) شروع → نتیجه: [(1,3)]
(2,6): 2 ≤ 3 همپوشان! → (1, max(3,6)) = (1,6)
(8,10): 8 > 6 جدا → افزودن
(15,18): 15 > 10 جدا → افزودن
خروجی: [(1,6), (8,10), (15,18)]نکته: پیچیدگی O(n log n) — مرتب‌سازی غالب است. اگر ورودی از قبل مرتب باشد، O(n)! در مسئله «درج فاصله» از همین استفاده کنید.
جمع‌بندی
- مرتب‌سازی بر اساس شروع = نصف مسئله
- ادغام: شروع فعلی ≤ پایان آخرین ← max پایان‌ها
- تقاطع: max شروع‌ها تا min پایان‌ها (اگر مثبت)
- کاربرد واقعی: تقویم، رزرو، زمان‌بندی
این مبحث بخشی از دوره آموزش کامل الگوریتم‌ها است.