Problem link ও উৎস
- **Original source:** Classic capstone interview problem (sort then sweep)
- **Platform:** LeetCode —
- **Topic:** sorting + arrays
- **Difficulty:** Medium
- **Pattern:** Sort by start, তারপর এক-পাসে overlap collapse (sweep)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **sorting** (interval-গুলোকে start দিয়ে sort করে একটা সাজানো timeline বানানো) আর **02 arrays** (সেই সাজানো list-এর উপর বাঁ-থেকে-ডান একবার scan করে পাশাপাশি জিনিস compare করা)। দুই tool জোড়া লাগলেই এই problem।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে কতগুলো interval দেওয়া আছে, প্রতিটা `[start, end]` রূপে — যেমন কোনো মিটিংয়ের শুরু আর শেষ সময়। এদের মধ্যে কিছু একে অন্যের সাথে ছুঁয়ে যায় বা overlap করে। তোমার কাজ: যেসব interval overlap করে, তাদের একসাথে জুড়ে একটা বড় interval বানাও, আর শেষে এমন একগুচ্ছ আলাদা (non-overlapping) interval ফেরত দাও যেগুলো একই জায়গা cover করে।
```text
intervals : [[1, 3], [2, 6], [8, 10], [15, 18]]
[1,3] আর [2,6] overlap করে -> জুড়ে [1,6]
ফলাফল : [[1, 6], [8, 10], [15, 18]]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[1,3],[2,6],[8,10],[15,18]] -> Output: [[1,6],[8,10],[15,18]]
Input : [[1,4],[4,5]] -> Output: [[1,5]] # ছোঁয়াও overlap (4 <= 4)
Edge case 1 (একটা interval): [[5,7]] -> [[5,7]]
Edge case 2 (একটা আরেকটাকে গেলে): [[1,10],[2,3]] -> [[1,10]]
Edge case 3 (unsorted input): [[2,6],[1,3]] -> [[1,6]] # আগে sort করতেই হবে
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তুমি সারাদিনের সব মিটিং একটা ক্যালেন্ডারে বসাচ্ছ, শুরুর সময় অনুযায়ী সাজিয়ে। নতুন একটা মিটিং নিলে দেখো — এটা কি আগের চলতি মিটিং শেষ হওয়ার আগেই শুরু হচ্ছে? হলে দুটো আসলে একটাই লম্বা ব্যস্ত-সময়, তাই শেষ সময়টা যেটা বেশি দূর সেটা রাখো। নাহলে আগের মিটিং শেষ, নতুন আলাদা একটা শুরু। দিনের শেষে তোমার হাতে থাকে কয়েকটা পরিষ্কার "ব্যস্ত block"।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem দুটো আগের chapter-এর tool জোড়া দেয়:
- **sorting** থেকে: interval-গুলোকে আগে **start time দিয়ে sort** করা। এক বার সাজানো হয়ে গেলে, যে interval-গুলো overlap করতে পারে তারা list-এ পাশাপাশি বসে — তখন আর সব pair মিলিয়ে দেখার দরকার নেই।
- **02 arrays** থেকে: সেই সাজানো array-র উপর **single pass** scan, যেখানে প্রতি step-এ শুধু "আগের জমানো interval" আর "এখনকার interval"-কে compare করি।
একা sorting দেয় "overlap-রা পাশাপাশি" এই গ্যারান্টি; একা array-scan দেয় পাশাপাশি জিনিস জোড়ার ক্ষমতা। দুটো মিললে O(n log n)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **overlap invariant**: যদি list start দিয়ে sorted হয়, তাহলে নতুন interval `[s, e]` আগের জমানো interval `[ps, pe]`-র সাথে overlap করে ঠিক তখনই যখন `s <= pe`। কারণ sort করায় `s >= ps` নিশ্চিত, তাই শুধু `s` যদি `pe`-র ভেতরে (বা সমান) পড়ে তবেই দুটো ছুঁয়ে আছে। overlap হলে নতুন end হয় `max(pe, e)` (একটা আরেকটাকে গিলে ফেলতে পারে, তাই max)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- ইনপুট হিসেবে interval-দের একটা **list/array** (02 arrays)।
- ফলাফল জমাতে আরেকটা **result list** (`merged`), যেটায় শেষ element-টাই বারবার "চলমান জমানো interval"-এর কাজ করে।
কোনো ভারী structure লাগে না — sort + একটা output list-ই যথেষ্ট।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
আমাদের শুধু দরকার "সর্বশেষ জমানো interval"-টাকে দ্রুত দেখা ও বাড়ানো। একটা result list-এর **শেষ element** (`merged[-1]`) ঠিক সেই কাজটা O(1)-এ করে — হয় তার `end` বাড়াই, নয় নতুন interval push করি। sort (03) overlap-দের পাশাপাশি এনে দেওয়ায় আমাদের কখনো পিছনে ফিরে তাকাতে হয় না, তাই এই append-only list-ই (02 arrays-এর সরল রূপ) নিখুঁত। এ কারণেই extra space শুধু output, আর কাজটা single pass।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: sort না করে বারবার পুরো list-টা ঘুরে দেখি কোনো দুটো interval overlap করছে কি না; পেলে তাদের জুড়ে দিই, আবার শুরু থেকে দেখি। কোনো overlap আর না পাওয়া পর্যন্ত repeat।
```text
repeat:
found = False
প্রতিটা pair (i, j):
if overlap(i, j):
ওদের জুড়ে একটা বানাও, দুটো মুছে যোগ করো
found = True; break
if not found: break
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার সব pair মেলানো **O(n^2)**, আর প্রতিটা merge-এর পর আবার শুরু থেকে — সব মিলিয়ে **O(n^3)** পর্যন্ত যেতে পারে। কারণ আমরা কোনো order ব্যবহার করছি না, তাই একই interval বারবার compare হয়। sort (03) একবার করে নিলে overlap-রা পাশাপাশি বসে, আর single pass-ই (02) যথেষ্ট হয়ে যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **start দিয়ে sort করলে, একটা interval কেবল তার ঠিক-আগের জমানো interval-এর সাথেই overlap করতে পারে — দূরের কারো সাথে নয়।** কারণ start বাড়ছে, তাই পরের কোনো interval আগের জমানোটার শুরুর আগে ঢুকতে পারে না। এই এক চিন্তাই O(n^2) compare-কে এক-পাসে নামিয়ে আনে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
interval-গুলো start দিয়ে sort করো। একটা খালি `merged` list রাখো। এক এক করে interval নাও: যদি `merged` খালি হয় বা এখনকার start আগের জমানোটার end-এর চেয়ে বড় হয় (gap আছে), নতুন interval হিসেবে push করো। নাহলে overlap — আগের জমানোটার end-কে `max(আগের end, এখনকার end)` করে বাড়াও। পুরো list শেষ হলে `merged`-ই উত্তর।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব pair overlap করে কি না দেখব" ভাবার বদলে আগে sort করে নাও — তখন প্রশ্নটা নেমে আসে শুধু "এখনকার start কি আগের end ছাড়িয়ে গেছে?"-তে। বিশাল pairwise তুলনা একটা সাজানো list-এর উপর single sweep-এ গলে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`[[1,3],[2,6],[8,10],[15,18]]` — start দিয়ে sort (এখানে আগেই sorted), তারপর sweep:
```text
sorted : [1,3] [2,6] [8,10] [15,18]
নাও [1,3] -> merged খালি, push merged = [[1,3]]
নাও [2,6] -> 2 <= 3 ? হ্যাঁ overlap end = max(3,6)=6 merged = [[1,6]]
নাও [8,10] -> 8 <= 6 ? না push merged = [[1,6],[8,10]]
নাও [15,18] -> 15 <= 10 ? না push merged = [[1,6],[8,10],[15,18]]
ফলাফল = [[1,6],[8,10],[15,18]]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[1,4],[2,3],[5,7]]`:
1. start দিয়ে sort: `[[1,4],[2,3],[5,7]]` (আগেই সাজানো); `merged = []`
2. নাও `[1,4]`: `merged` খালি → push; `merged = [[1,4]]`
3. নাও `[2,3]`: `2 <= 4` → overlap; end = `max(4, 3) = 4`; `merged = [[1,4]]`
4. নাও `[5,7]`: `5 <= 4`? না → push; `merged = [[1,4],[5,7]]`
5. শেষ → return `[[1,4],[5,7]]`
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def merge_intervals(intervals):
if not intervals:
return []
intervals.sort(key=lambda iv: iv[0]) # start দিয়ে sort (sorting)
merged = [intervals[0][:]] # প্রথমটা দিয়ে শুরু (copy)
for s, e in intervals[1:]: # বাকিগুলো একবার scan (02 arrays)
if s <= merged[-1][1]: # এখনকার start আগের end-এর ভেতরে?
merged[-1][1] = max(merged[-1][1], e) # overlap -> end বাড়াও
else:
merged.append([s, e]) # gap -> নতুন interval
return merged
# ---- tests ----
assert merge_intervals([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
assert merge_intervals([[1,4],[4,5]]) == [[1,5]] # ছোঁয়াও overlap
assert merge_intervals([[5,7]]) == [[5,7]] # একটা interval
assert merge_intervals([[1,10],[2,3]]) == [[1,10]] # একটা আরেকটাকে গেলে
assert merge_intervals([[2,6],[1,3]]) == [[1,6]] # unsorted input
assert merge_intervals([]) == [] # খালি
assert merge_intervals([[1,4],[0,4]]) == [[0,4]] # একই end, ছোট start
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not intervals: return []` — খালি ইনপুটে আগেভাগে খালি list ফেরত, পরের `intervals[0]` যেন crash না করে।
- `intervals.sort(key=lambda iv: iv[0])` — start দিয়ে সাজাও; এতেই overlap-রা পাশাপাশি বসে (sorting)।
- `merged = [intervals[0][:]]` — প্রথম interval-এর একটা copy দিয়ে শুরু (`[:]` যাতে মূল ইনপুট না বদলায়)।
- `for s, e in intervals[1:]` — দ্বিতীয় থেকে একবার scan (02 arrays-এর single pass)।
- `if s <= merged[-1][1]` — এখনকার start আগের জমানোটার end-এর ভেতরে হলে overlap।
- `merged[-1][1] = max(...)` — overlap হলে শেষ জমানোটার end-কে দূরতমটা দিয়ে বাড়াই (একটা আরেকটাকে গিলতে পারে)।
- `else: merged.append([s, e])` — gap থাকলে আলাদা নতুন interval।
- `return merged` — সব মিলিয়ে non-overlapping interval-দের list।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[[1,3],[2,6],[8,10],[15,18]]`-এ sort করার পর `[1,3]` দিয়ে শুরু; `[2,6]`-এ `2 <= 3` তাই end হয় 6 → `[1,6]`; `[8,10]`-এ `8 <= 6` মিথ্যা, তাই আলাদা push; `[15,18]`-ও তাই → `[[1,6],[8,10],[15,18]]` — assert pass। ছোঁয়া-overlap (`4 <= 4`), গিলে ফেলা, unsorted, খালি — সব case সঠিক। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — মূল খরচ sort-এ; তার পরের sweep মাত্র O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — output `merged` list সবচেয়ে খারাপ ক্ষেত্রে n-টা interval রাখে (যদি কেউ overlap না করে)। in-place sort ধরলে বাড়তি কাজের memory O(1) (sort-এর নিজস্ব খরচ বাদে)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- sort করতে ভুলে যাওয়া — তাহলে "শুধু আগের জমানোটার সাথে compare" যুক্তিটাই ভেঙে যায়।
- overlap শর্তে `<` ব্যবহার করা (`s < pe`) — তখন ছোঁয়া interval (`[1,4]` আর `[4,5]`) জোড়া পড়ে না; `<=` লাগে যদি ছোঁয়াকেও overlap ধরো।
- end বাড়াতে `max` না নিয়ে সরাসরি `e` বসানো — `[1,10]` আর `[2,3]`-এ end ভুল করে 3 হয়ে যাবে; দূরতমটা রাখতে `max` জরুরি।
- মূল ইনপুট list সরাসরি বদলে ফেলা — copy (`[:]`) রাখলে side-effect এড়ানো যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: comparator দিয়ে sorting (sorting, [পূর্বশর্ত](../../02-arrays-and-strings/README.md)) + সাজানো array-র উপর single-pass scan আর পাশাপাশি compare (02 arrays, [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))। এই দুটো cold জানা থাকলে "sort তারপর sweep" নিজে থেকেই আসে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Insert Interval (একটা নতুন interval ঢুকিয়ে আবার merge) —