Problem link ও উৎস
- **Original source:** Classic technique (imos method — interval event counting)
- **Platform:** Classic technique (imos method) —
- **Topic:** Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
- **Difficulty:** Medium
- **Pattern:** imos method (interval → +1/−1 events → prefix)
- **Basic idea inherited from:** 069 — Difference Array
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কিছু interval (অন্তর্বর্তী সময়) দেওয়া — প্রতিটা `[l, r]` মানে "সময় l থেকে r পর্যন্ত (দুই প্রান্ত সহ) একজন উপস্থিত"। তোমাকে বলতে হবে — প্রতিটা সময় বিন্দুতে (0 থেকে T-1) **মোট কতজন একসাথে উপস্থিত**?
যেমন interval `[(0,2), (1,3), (4,4)]`, T=5 হলে প্রতিটা সময়ে উপস্থিতি: `[1, 2, 2, 1, 1]` — সময় 1 আর 2-এ দুজন overlap করছে। এটা imos method-এর ভিত্তি; এই count থেকে "সর্বোচ্চ একসাথে কতজন" বা "কোন সময়ে কেউ নেই"-ও সহজে বের হয়।
### Input ও output {#6-example-input-and-output}
```text
intervals T -> counts
-----------------------------------------------------
[(0,2), (1,3), (4,4)] 5 -> [1, 2, 2, 1, 1]
[(0,4)] 5 -> [1, 1, 1, 1, 1] (একজন সারা সময়)
[(1,1), (1,1)] 3 -> [0, 2, 0] (দুজন একই বিন্দুতে)
[(0,0), (2,2)] 3 -> [1, 0, 1] (মাঝে কেউ নেই)
[] 3 -> [0, 0, 0] (কোনো interval নেই)
সর্বোচ্চ overlap = max(counts); উপরের প্রথমটায় = 2
```
Edge case: একই বিন্দুতে একাধিক ঢোকা (`[(1,1),(1,1)]` → time 1-এ 2) — diff স্বাভাবিকভাবেই জমা করে। আর `r+1` যেন array-র বাইরে না যায়, সেজন্য diff দৈর্ঘ্য T+1।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পার্টি হল, আর একটা গণনা-যন্ত্র দরজায়। প্রতিজন অতিথি একটা সময়ে ঢোকে আর একটা সময়ে বেরোয়।
তুমি প্রতিটা অতিথির পুরো উপস্থিত-সময় ধরে গোনার বদলে, শুধু **দরজার ঘটনা** লিখে রাখো: কেউ ঢুকলে "+1", বেরোলে "−1"। দিনের শেষে এই ঘটনাগুলো সময় অনুযায়ী সাজিয়ে, শুরু থেকে একটা running count রাখো — "+1 দেখলে বাড়াও, −1 দেখলে কমাও"। প্রতিটা মুহূর্তে এই count-ই বলে দেয় হলে তখন কতজন ছিল।
দরজার দুটো ঘটনা (ঢোকা, বেরোনো) দিয়ে পুরো উপস্থিতি-সময় সামলে গেল — ভেতরের প্রতিটা মুহূর্ত আলাদা গোনা লাগল না। এটাই imos: ব্যবধানকে দুটো event-এ নামানো, তারপর running total।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি **069 (Difference Array)** থেকে — হুবহু সেই "দুই প্রান্তে দাগ, শেষে prefix" কৌশল। পার্থক্য শুধু দৃষ্টিভঙ্গিতে: 069-এ ছিল "range-এ x যোগ করো"; এখানে "interval = একজন উপস্থিত, +1"।
069-এর update ছিল arbitrary `x`; imos-এ `x = +1` (ঢোকা) আর `−1` (বেরোনো) — মানুষ গোনা। তাই imos = difference array-র event-রূপ। এই অনুবাদ — "ব্যবধান মানে দুটো প্রান্তিক ঘটনা" — পরবর্তী sweep line (080)-এর সরাসরি ভিত্তি। 069 না বুঝলে imos রহস্যময় লাগবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea হলো **imos method** — একটা interval-কে দুটো event-এ ভাঙা, তারপর prefix sum।
প্রতিটা interval `[l, r]` মানে: সময় `l`-এ একজন **ঢুকল** (+1), সময় `r+1`-এ একজন **বেরোল** (−1)। এটা ঠিক difference array (069):
```text
diff[l] += 1 (ঢোকা)
diff[r + 1] -= 1 (বেরোনো)
```
সব interval-এর event বসিয়ে, এক pass prefix sum চালালে প্রতিটা সময়ে "ভেতরে কতজন" বেরিয়ে আসে — কারণ prefix হলো "এ পর্যন্ত মোট +1 আর −1-এর যোগফল" = এখন ভেতরে কতজন। difference নেয় event, prefix বানায় count।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
প্রতিটা interval ধরে তার পুরো range-এ প্রতিটা সময়ে +1:
```python
def imos_brute(intervals, T):
counts = [0] * T
for l, r in intervals:
for t in range(l, r + 1): # interval-এর প্রতিটা সময়ে +1
counts[t] += 1
return counts
```
সরল, ঠিক উত্তর — প্রতিটা interval তার প্রতিটা সময়-বিন্দুতে একজন যোগ করে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
একটা interval-এ ভেতরের loop চলে `(r - l + 1)` বার — খারাপ ক্ষেত্রে পুরো timeline, O(T)। m টা interval হলে মোট **O(m × T)**।
```text
m = 100000, T = 100000 হলে:
brute force: ~10^10 operation (O(m·T)) — TLE
imos way : m × O(1) (দুটো event) + O(T) prefix ≈ 3×10^5 — দ্রুত
```
069-এর মতোই অপচয়: একই সময়-বিন্দু বহু interval-এ বারবার +1 পাচ্ছে। অথচ দরকার শুধু "কোথায় ঢোকা, কোথায় বেরোনো" — মাঝের প্রতিটা বিন্দু আলাদা ছোঁয়ার দরকার নেই।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight: interval = দুটো event (ঢোকা +1, বেরোনো −1)। সব event difference array-তে O(1) করে বসাও, একবার prefix চালিয়ে প্রতি সময়ের count:
```python
def imos_counts(intervals, T):
diff = [0] * (T + 1) # r+1 এর জায়গা
for l, r in intervals:
diff[l] += 1 # ঢোকা
diff[r + 1] -= 1 # বেরোনো (r+1-এ)
counts = [0] * T
run = 0
for t in range(T):
run += diff[t] # prefix = এখন কতজন
counts[t] = run
return counts
```
m টা O(1) event + একটা O(T) prefix pass = **O(m + T)**। brute-এর m×T থেকে বিশাল লাফ।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত: **একটা ব্যবধান (interval) আসলে দুটো প্রান্তিক ঘটনা — শুরুতে +1, শেষের পরে −1।** পুরো উপস্থিতি-সময়কে দুটো event-এ নামিয়ে আনা, তারপর running total দিয়ে প্রতি মুহূর্তের অবস্থা ফেরানো।
এটা 069-এরই দৃষ্টিভঙ্গি-বদল: range update (069) আর "কতজন উপস্থিত" (imos) — একই difference+prefix, ভিন্ন গল্প। আর এই "ব্যবধান → event" অনুবাদটাই পরের ধাপ sweep line (080)-এর বীজ: timeline যখন বিশাল বা বিক্ষিপ্ত, তখন array-র বদলে শুধু event গুলো sort করে হাঁটব।
### ছবিতে বোঝা {#5-visual-explanation}
interval `[(0,2), (1,3), (4,4)]`, T=5। difference array `diff` (দৈর্ঘ্য T+1=6):
```text
শুরু: diff = [0, 0, 0, 0, 0, 0]
[0,2]: diff[0]+=1, diff[3]-=1 → [1, 0, 0, -1, 0, 0]
[1,3]: diff[1]+=1, diff[4]-=1 → [1, 1, 0, -1, -1, 0]
[4,4]: diff[4]+=1, diff[5]-=1 → [1, 1, 0, -1, 0, -1]
prefix চালিয়ে (running count = এখন কতজন ভেতরে):
time t: 0 1 2 3 4
diff[t]: 1 1 0 -1 0
running: 1 → 2 → 2 → 1 → 1
counts = [ 1, 2, 2, 1, 1 ]
```
ছবিটা ধরো: time 1-এ দ্বিতীয় অতিথি ঢুকল (count 1→2), time 3-এ প্রথমজন বেরোল (count 2→1)। interval `[0,2]`-এর "বেরোনো" দাগ গেল `diff[3]`-এ (r+1=3), কারণ time 2 পর্যন্ত সে উপস্থিত। প্রতিটা +1/−1 event timeline-এ সঠিক জায়গায়।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
interval `[(0,2), (1,3), (4,4)]`, T=5। `diff = [0,0,0,0,0,0]` (দৈর্ঘ্য 6):
Event বসানো:
| interval | diff পরিবর্তন | diff এখন |
| --- | --- | --- |
| (0,2) | diff[0]+=1, diff[3]-=1 | [1, 0, 0, -1, 0, 0] |
| (1,3) | diff[1]+=1, diff[4]-=1 | [1, 1, 0, -1, -1, 0] |
| (4,4) | diff[4]+=1, diff[5]-=1 | [1, 1, 0, -1, 0, -1] |
prefix (running count):
| t | diff[t] | run | counts[t] |
| --- | --- | --- | --- |
| 0 | 1 | 1 | 1 |
| 1 | 1 | 2 | 2 |
| 2 | 0 | 2 | 2 |
| 3 | -1 | 1 | 1 |
| 4 | 0 | 1 | 1 |
শেষ অবস্থা: `counts = [1, 2, 2, 1, 1]`। সর্বোচ্চ overlap = 2 (time 1, 2)। brute force-ও একই দেয় ✓।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def imos_counts(intervals, T):
"""প্রতিটা সময়-বিন্দু (0..T-1)-এ কতজন উপস্থিত; imos = difference + prefix, O(m + T)।
interval [l, r] inclusive: ঢোকা diff[l] += 1, বেরোনো diff[r+1] -= 1।"""
diff = [0] * (T + 1)
for l, r in intervals:
diff[l] += 1
diff[r + 1] -= 1
counts = [0] * T
run = 0
for t in range(T):
run += diff[t]
counts[t] = run
return counts
def imos_brute(intervals, T):
"""ধীর O(m·T) version — interval ধরে প্রতি বিন্দুতে +1; মিলিয়ে দেখার জন্য।"""
counts = [0] * T
for l, r in intervals:
for t in range(l, r + 1):
counts[t] += 1
return counts
# --- ছোট test গুলো (সব pass করা উচিত) ---
assert imos_counts([(0, 2), (1, 3), (4, 4)], 5) == [1, 2, 2, 1, 1]
assert imos_counts([(0, 4)], 5) == [1, 1, 1, 1, 1]
assert imos_counts([(1, 1), (1, 1)], 3) == [0, 2, 0] # একই বিন্দুতে দুজন
assert imos_counts([(0, 0), (2, 2)], 3) == [1, 0, 1] # মাঝে কেউ নেই
assert imos_counts([], 3) == [0, 0, 0] # কোনো interval নেই
# সর্বোচ্চ overlap = max(counts):
assert max(imos_counts([(0, 2), (1, 3), (4, 4)], 5)) == 2
# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(37)
for _ in range(500):
T = random.randint(1, 12)
m = random.randint(0, 6)
intervals = []
for _ in range(m):
l = random.randint(0, T - 1)
r = random.randint(l, T - 1)
intervals.append((l, r))
assert imos_counts(intervals, T) == imos_brute(intervals, T)
print(imos_counts([(0, 2), (1, 3), (4, 4)], 5)) # [1, 2, 2, 1, 1]
print(max(imos_counts([(0, 2), (1, 3), (4, 4)], 5))) # 2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
diff = [0] * (T + 1)
```
difference array, T+1 ঘর — বাড়তি ঘরটা `diff[r+1]`-এর জন্য, যখন `r = T-1`।
```text
for l, r in intervals:
diff[l] += 1
diff[r + 1] -= 1
```
প্রতিটা interval দুটো event-এ: `l`-এ ঢোকা (+1), `r+1`-এ বেরোনো (−1)। range যত বড়ই হোক, দুটো দাগ — তাই O(1)। (069-এর `x`-এর জায়গায় এখানে +1।)
```text
run = 0
for t in range(T):
run += diff[t]
counts[t] = run
```
prefix sum — running count রাখছি, যা প্রতিটা সময়ে "এ পর্যন্ত মোট ঢোকা − বেরোনো" = এখন কতজন ভেতরে। +1 event count বাড়ায়, −1 কমায়।
বাকি `assert` গুলো নির্দিষ্ট উদাহরণ + random interval-এ fast আর brute মিলিয়ে দেখছে (brute-force cross-check), max-overlap সহ। সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
`intervals = [(0,2), (1,3), (4,4)], T=5`:
- event বসানো: `diff = [1, 1, 0, -1, 0, -1]`
- prefix: run যায় `1, 2, 2, 1, 1` → `counts = [1, 2, 2, 1, 1]` → প্রথম `print`
- `max(counts) = 2` → দ্বিতীয় `print`
- সব `assert` pass → `সব test pass!`
ছাপা output:
```text
[1, 2, 2, 1, 1]
2
সব test pass!
```
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(m + T)** — m টা interval প্রতিটা O(1) (দুটো event), তারপর একটা O(T) prefix pass। brute-এর O(m × T)-এর তুলনায় বিশাল উন্নতি, বিশেষত লম্বা interval-এ।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(T)** — difference array (T+1) আর counts array (T)। interval সংখ্যার উপর আলাদা জায়গা লাগে না (event সরাসরি diff-এ জমে)।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`diff[r+1] -= 1` এর জায়গায় `diff[r] -= 1`** — তাহলে time `r`-এর অতিথিও গোনা বন্ধ হয়ে যায়, যদিও সে `r`-এ উপস্থিত। inclusive interval-এ বেরোনো `r+1`-এ।
2. **diff দৈর্ঘ্য T (T+1 না)** — `r = T-1` হলে `diff[r+1] = diff[T]` out-of-range; T+1 রাখো।
3. **inclusive vs exclusive interval গুলিয়ে ফেলা** — `[l, r]` inclusive হলে `r+1`-এ −1; `[l, r)` exclusive হলে `r`-এ −1। প্রশ্নের convention মিলাও।
4. **event আর count-এর ক্রম** — সব interval-এর event আগে বসাও, *তারপর* prefix; মাঝপথে count পড়লে ভুল।
5. **max overlap-এ prefix না চালানো** — শুধু diff-এ max নিলে ভুল; "একসাথে কতজন" পেতে prefix (running count)-এর উপর max।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Car Pooling** (