Problem link ও উৎস
- **Original source:** Classic technique (sweep line — sorted events)
- **Platform:** Classic technique —
(এবং LeetCode Meeting Rooms II — )
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** sweep line (sort +1/−1 events, running count)
- **Basic idea inherited from:** 079 — Imos Method Basic
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কিছু interval দেওয়া — প্রতিটা `[l, r)` মানে একটা কাজ/মিটিং যা সময় `l`-এ শুরু হয়ে `r`-এ শেষ (half-open: `r` বিন্দুতে আর চলছে না)। তোমাকে বলতে হবে — **কোনো এক মুহূর্তে সর্বোচ্চ কতগুলো interval একসাথে চলছে?** (এটাই, যেমন, কয়টা meeting room লাগবে।)
যেমন `[(1,4), (2,5), (3,6)]` হলে উত্তর 3 — সময় 3-এর কাছাকাছি তিনটাই একসাথে চলছে। coordinate বড় হতে পারে, তাই 079-এর মতো প্রতিটা সময়-বিন্দুর array বানানো যাবে না; শুধু event ধরে কাজ করতে হবে।
### Input ও output {#6-example-input-and-output}
```text
intervals (half-open [l, r)) -> max overlap
-----------------------------------------------------
[(1,4), (2,5), (3,6)] -> 3
[(1,2), (2,3), (3,4)] -> 1 (শুধু ছোঁয়, overlap নয়)
[(0,10)] -> 1
[(1,3), (1,3), (1,3)] -> 3 (তিনটাই একই, পুরো overlap)
[(0,1), (1,2), (0,2)] -> 2
[] -> 0 (কোনো interval নেই)
```
সবচেয়ে গুরুত্বপূর্ণ edge case: **tie at same coordinate.** half-open `[l, r)`-এ একই বিন্দুতে শেষ আর শুরু মিললে শেষ আগে (−1 before +1) — তাই `[(1,2),(2,3)]` overlap নয়, উত্তর 1। closed interval `[l, r]` চাইলে উল্টো (শুরু আগে) — convention অনুযায়ী tie-নিয়ম বদলায়।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা ব্যস্ত হাসপাতালের OPD, আর তুমি জানতে চাও সর্বোচ্চ কতজন রোগী একসাথে ভেতরে ছিল — যাতে কতটা চেয়ার লাগবে বোঝা যায়। কিন্তু দিনটা লম্বা, প্রতি সেকেন্ড গোনা বোকামি।
বরং শুধু **দরজার ঘটনা** লেখো: কে কখন ঢুকল, কে কখন বেরোল। তারপর সব ঘটনা সময় অনুযায়ী সাজিয়ে, একটা কল্পিত ঘড়ি বাঁ থেকে ডানে চালাও — ঢোকা দেখলে গণনা +1, বেরোনো দেখলে −1। চলার পথে যে সর্বোচ্চ সংখ্যায় পৌঁছালে, ততগুলো চেয়ার লাগবে।
পুরো দিন নয়, শুধু ঘটনার মুহূর্তগুলোতে থামলেই চলে — কারণ দুই ঘটনার মাঝে সংখ্যা বদলায় না। এই "শুধু পরিবর্তন-বিন্দুতে থামা ঝাড়ু" হলো sweep line।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **079 (Imos Method Basic)** থেকে। 079-এ event বসত একটা array-র index-এ (`diff[l] += 1`), তারপর prefix। এখানে timeline বিশাল/বিক্ষিপ্ত বলে array নেই — event গুলো **sort** করে সেই prefix-চিন্তাই sorted order-এ চালাই।
মূল পার্থক্য: imos-এর `diff` array index-ভিত্তিক (O(T) জায়গা), sweep-এর event list coordinate-ভিত্তিক (O(m) জায়গা, T-নিরপেক্ষ)। তাই বিশাল coordinate-এ sweep চলে, imos চলে না। প্রায় coordinate compression-এর ধারণা — শুধু যেখানে বদল, সেই বিন্দু। 079-এর event-চিন্তা না থাকলে এই sort-ভিত্তিক রূপ বোঝা কঠিন।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **sweep line** — সব শুরু/শেষ-কে event বানিয়ে sort করে, একটা কল্পিত উল্লম্ব রেখা বাঁ থেকে ডানে "ঝাড়ু" দেওয়া।
প্রতিটা interval `[l, r)` থেকে দুটো event: `(l, +1)` (শুরু) আর `(r, −1)` (শেষ)। সব event coordinate অনুযায়ী sort করো। তারপর বাঁ থেকে ডানে যেতে যেতে একটা `cur` (এখন কয়টা চলছে) রাখো — `+1`-এ বাড়াও, `−1`-এ কমাও। পথে সর্বোচ্চ `cur`-ই উত্তর:
```text
events = [(l, +1) for each] + [(r, -1) for each]
sort events; cur += delta; best = max(best, cur)
```
এটা imos-এরই (079) sorted-event রূপ — array-র জায়গায় sorted list, প্রতিটা সময়-বিন্দু নয় শুধু "যেখানে কিছু বদলায়" সেই বিন্দুগুলো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রতিটা সম্ভাব্য বিন্দু (interval-এর শুরুগুলো যথেষ্ট) ধরে গুনি কতগুলো interval সেটা ঢাকে:
```python
def max_overlap_brute(intervals):
if not intervals:
return 0
best = 0
for l, r in intervals: # candidate বিন্দু = প্রতিটা শুরু
count = sum(1 for a, b in intervals if a <= l < b) # half-open
best = max(best, count)
return best
```
সরল, ঠিক উত্তর — প্রতিটা শুরু-বিন্দুতে কতগুলো interval চলছে গোনে (max overlap সবসময় কোনো শুরু-বিন্দুতে ঘটে)।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
প্রতিটা candidate বিন্দুর (m টা) জন্য সব interval (m টা) চেক — **O(m²)**।
```text
m = 100000 হলে:
brute force: ~10^10 operation (O(m²)) — TLE
sweep way : ~m log m ≈ 1.7×10^6 — দ্রুত
```
অপচয়টা: প্রতিটা বিন্দুতে সব interval আবার গোনা। অথচ event sort করে একবার হাঁটলেই running count পাওয়া যায় — প্রতিটা interval মাত্র দুবার (শুরু, শেষ) ছোঁয়া হয়।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: সব শুরু/শেষ-কে event বানাও, sort করো, একবার হেঁটে running count-এর max নাও:
```python
def max_overlap(intervals):
events = []
for l, r in intervals:
events.append((l, 1)) # শুরু
events.append((r, -1)) # শেষ
events.sort(key=lambda e: (e[0], e[1])) # tie: -1 (শেষ) আগে +1 (শুরু)
best = cur = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
```
event বানানো O(m), sort O(m log m), হাঁটা O(m) — মোট **O(m log m)**। O(m²) থেকে নেমে এল।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
দুটো "আহা!" মুহূর্ত।
প্রথম: **পুরো timeline নয়, শুধু পরিবর্তন-বিন্দু (event) দেখো।** দুই event-এর মাঝে overlap সংখ্যা বদলায় না, তাই array না বানিয়ে শুধু event sort করে হাঁটলেই চলে — এটাই imos (079)-কে বিশাল/বিক্ষিপ্ত coordinate-এ টেনে নেয়।
দ্বিতীয় (সবচেয়ে সূক্ষ্ম): **tie-এর নিয়ম convention-নির্ভর।** half-open `[l, r)`-এ একই বিন্দুতে শেষ(−1) আগে, শুরু(+1) পরে — তাই শুধু-ছোঁয়া interval overlap গোনে না। closed `[l, r]`-এ উল্টো। sort-key-তে `(coord, delta)` দিয়ে এটা সামলাই (−1 < +1, তাই −1 আগে)। এই একটা সিদ্ধান্তই tie-bug-এর রক্ষাকবচ — interval problem-এ এখানেই সবচেয়ে বেশি ভুল হয়।
### ছবিতে বোঝা {#5-visual-explanation}
`[(1,4), (2,5), (3,6)]` (half-open `[l, r)`)। event বানিয়ে sort:
```text
interval [1,4): (1, +1), (4, -1)
interval [2,5): (2, +1), (5, -1)
interval [3,6): (3, +1), (6, -1)
sort করে (coordinate বাড়ন্ত; tie হলে -1 আগে, +1 পরে):
(1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)
বাঁ থেকে ডানে ঝাড়ু (cur = এখন কয়টা চলছে):
event: (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)
cur: 1 2 3 2 1 0
best: 1 2 3 3 3 3
সর্বোচ্চ overlap = 3 (সময় 3-এর পর তিনটাই একসাথে)
```
আর touching interval-এর ছবি (`[1,2), [2,3)` — শুধু ছুঁয়ে আছে, overlap নয়):
```text
events sort: (1,+1) (2,-1) (2,+1) (3,-1)
↑ tie at 2: -1 আগে!
cur: 1 0 1 0
best = 1 (ঠিক — ওরা overlap করে না, শুধু ছোঁয়)
```
মূল কথা: একই coordinate-এ শেষ (−1) আর শুরু (+1) থাকলে, half-open interval-এ **শেষ আগে** process করো — নইলে শুধু-ছোঁয়া interval-কে ভুল করে overlap গুনবে।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`[(1,4), (2,5), (3,6)]` (half-open)। event বানিয়ে sort:
```text
events (sort করা): (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)
```
ঝাড়ু:
| event | delta | cur += delta | best |
| --- | --- | --- | --- |
| (1, +1) | +1 | 1 | 1 |
| (2, +1) | +1 | 2 | 2 |
| (3, +1) | +1 | 3 | 3 |
| (4, -1) | -1 | 2 | 3 |
| (5, -1) | -1 | 1 | 3 |
| (6, -1) | -1 | 0 | 3 |
শেষ অবস্থা: `best = 3`। সময় 3-এর পর তিনটাই একসাথে চলছিল; তারপর একে একে শেষ হলো। brute force-ও 3 দেয় ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def max_overlap(intervals):
"""সর্বোচ্চ কতগুলো half-open interval [l, r) একসাথে; sweep line, O(m log m)।
tie at same coordinate: শেষ(-1) আগে, শুরু(+1) পরে — touching overlap নয়।"""
events = []
for l, r in intervals:
events.append((l, 1))
events.append((r, -1))
events.sort(key=lambda e: (e[0], e[1])) # -1 < +1, তাই শেষ আগে
best = cur = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
def max_overlap_brute(intervals):
"""ধীর O(m^2) version — প্রতিটা শুরু-বিন্দুতে গোনা; মিলিয়ে দেখার জন্য।"""
if not intervals:
return 0
best = 0
for l, r in intervals:
count = sum(1 for a, b in intervals if a <= l < b)
best = max(best, count)
return best
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert max_overlap([(1, 4), (2, 5), (3, 6)]) == 3
assert max_overlap([(1, 2), (2, 3), (3, 4)]) == 1 # শুধু ছোঁয়, overlap নয়
assert max_overlap([(0, 10)]) == 1
assert max_overlap([(1, 3), (1, 3), (1, 3)]) == 3 # পুরো overlap
assert max_overlap([(0, 1), (1, 2), (0, 2)]) == 2
assert max_overlap([]) == 0 # কোনো interval নেই
# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(41)
for _ in range(500):
intervals = []
for _ in range(random.randint(0, 8)):
l = random.randint(0, 10)
r = random.randint(l + 1, 11) # half-open, r > l নিশ্চিত
intervals.append((l, r))
assert max_overlap(intervals) == max_overlap_brute(intervals)
print(max_overlap([(1, 4), (2, 5), (3, 6)])) # 3
print(max_overlap([(1, 2), (2, 3), (3, 4)])) # 1
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
for l, r in intervals:
events.append((l, 1))
events.append((r, -1))
```
প্রতিটা interval দুটো event-এ ভাঙছি: শুরু `(l, +1)`, শেষ `(r, −1)`। পুরো interval নয়, শুধু দুই প্রান্তিক ঘটনা।
```text
events.sort(key=lambda e: (e[0], e[1]))
```
coordinate অনুযায়ী sort; tie হলে দ্বিতীয় key `delta` — `-1 < +1`, তাই একই বিন্দুতে শেষ আগে process হয় (half-open convention)। এই sort-key-ই tie-bug সামলায়।
```text
best = cur = 0
for _, delta in events:
cur += delta
best = max(best, cur)
```
বাঁ থেকে ডানে ঝাড়ু — `cur` এখন কয়টা চলছে (+1-এ বাড়ে, −1-এ কমে), পথে সর্বোচ্চ `best`-এ রাখি। এটাই running count-এর max, imos-এর prefix-max-এর sorted রূপ।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + random interval-এ fast আর brute মিলিয়ে দেখছে (brute-force cross-check), touching ও পুরো-overlap সহ। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`[(1,4), (2,5), (3,6)]`:
- events sort: `(1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)`
- ঝাড়ু: cur যায় `1, 2, 3, 2, 1, 0`, best = 3 → প্রথম `print`
- `[(1,2),(2,3),(3,4)]` → touching, best = 1 → দ্বিতীয় `print`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
3
1
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(m log m)** — m টা interval থেকে 2m টা event, sort-এর খরচ O(m log m); তারপর একবার হাঁটা O(m)। sort-ই প্রধান খরচ। brute-এর O(m²) থেকে বড় উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(m)** — event list-এ 2m টা entry। লক্ষণীয়: এটা coordinate-এর আকার (T)-নিরপেক্ষ — imos-এর O(T)-র বদলে O(m), তাই বিশাল/বিক্ষিপ্ত timeline-এও চলে।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **tie-এর নিয়ম ভুল করা** — half-open `[l, r)`-এ একই বিন্দুতে শেষ আগে (−1 before +1); নাহলে touching interval ভুল করে overlap গোনে। sort-key `(coord, delta)` এটা ঠিক করে।
2. **closed vs half-open গুলিয়ে ফেলা** — closed `[l, r]`-এ শুরু আগে (tie উল্টো); convention মিলিয়ে নাও, নইলে প্রান্তে off-by-one।
3. **imos array দিয়ে বিশাল coordinate সামলানোর চেষ্টা** — coordinate 10^9 হলে array বানানো অসম্ভব; event sort করো (বা coordinate compression)।
4. **running max নিতে ভুলে যাওয়া** — শুধু শেষ `cur` নয়, পথে সর্বোচ্চ `cur` চাই; প্রতি step-এ `best = max(best, cur)`।
5. **শেষ point (r) overlap-এ গোনা (half-open-এ)** — `[l, r)`-এ `r` বিন্দুতে interval চলছে না; brute-এ `a <= p < b` (`<= b` নয়)।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Meeting Rooms II** (