Problem link ও উৎস
- **Original source:** LeetCode 732 — My Calendar III
- **Platform:** LeetCode —
- **Topic:** segment tree and fenwick tree
- **Difficulty:** Hard
- **Pattern:** sweep line / lazy-tree teaser (interval-এ +1, max overlap track)
- **Basic idea inherited from:** intervals, segment-on-values
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা calendar-এ একে একে event বুক করা হচ্ছে। প্রতিটা event একটা half-open interval `[start, end)` — অর্থাৎ `start` থেকে শুরু, কিন্তু `end` ছোঁয় না।
প্রতিবার একটা নতুন event যোগ করার পর বলতে হবে: এই মুহূর্ত পর্যন্ত যত event যোগ হয়েছে, তাদের মধ্যে কোনো একটা সময়-বিন্দুতে সর্বোচ্চ কতগুলো event একসাথে চলছে (maximum overlap / `k`-booking)।
```text
book [10, 20) -> 1 (এক জায়গাতেই একটা)
book [50, 60) -> 1 (আলাদা সময়, এখনো max 1)
book [10, 40) -> 2 ([10,20) আর [10,40) ওভারল্যাপ করছে)
book [ 5, 15) -> 3 ([10,15)-এ তিনটাই চলছে)
book [ 5, 10) -> 3
book [25, 55) -> 3
```
### Input ও output {#8-example-input-and-output}
```text
book [10, 20) -> 1
book [50, 60) -> 1
book [10, 40) -> 2
book [ 5, 15) -> 3
book [ 5, 10) -> 3
book [25, 55) -> 3
half-open মনে রেখো: [5,10) আর [10,20) overlap করে না (10 ছোঁয় না)।
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা meeting room-এর সারাদিনের timeline একটা লম্বা টেপের মতো টানানো। প্রতিটা নতুন meeting এলে তুমি তার শুরু-বিন্দুতে একটা "+1" sticker আর শেষ-বিন্দুতে একটা "−1" sticker সাঁটো।
দিনের কোন মুহূর্তে সবচেয়ে ভিড় জানতে তুমি বাঁ থেকে ডান টেপ বরাবর হাঁটো, sticker-গুলো যোগ করতে করতে একটা চলমান গোনা রাখো — সেই গোনা যেখানে সর্বোচ্চ, সেটাই দিনের সবচেয়ে ব্যস্ত মুহূর্ত। প্রতিটা ঘরের প্রতি মিনিট আলাদা করে গুনতে হয় না।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **intervals** আর **segment-on-values**-এর উপর।
- **Intervals** থেকে: একটা interval `[s, e)`-কে দুটো ঘটনা হিসেবে দেখা — `s`-এ "একটা event শুরু" (+1), `e`-তে "একটা event শেষ" (−1)। এটাই classic **sweep line / difference-array** চিন্তা ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md))।
- **Segment-on-values** থেকে: events টাইম-axis-এর উপর +1/−1 করে; কোনো বিন্দুতে চলমান event-সংখ্যা মানে ওই বিন্দু পর্যন্ত prefix sum, আর আমরা চাই সব বিন্দুর সর্বোচ্চ prefix sum — যেটা range-update + range-max segment tree বা সহজ difference-array-তে বেরোয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **difference array / sweep**: interval `[s, e)`-এ "+1 everywhere" করা মানে শুধু `s`-এ `+1` আর `e`-তে `−1` লেখা। সব ঘটনা সময়-অনুযায়ী sort করে বাঁ-থেকে-ডান prefix sum চালালে, যেকোনো মুহূর্তে চলমান event-সংখ্যা বেরিয়ে আসে; সেই prefix sum-এর সর্বোচ্চ মান-ই উত্তর।
পুরো segment-tree version এই "interval-এ +1, global max"-কেই **lazy propagation** দিয়ে করে — একটা node-এর পুরো segment cover হলে নিচে না নেমে গায়ে "+1" sticky note লেখা ([../segment-tree.md](../segment-tree.md) section 9-এর teaser)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো পথ, একই উত্তর:
- **Teaser path (clean):** একটা **sorted map** (key = time-point, value = net change)। প্রতিটা booking-এ `delta[s] += 1`, `delta[e] -= 1`; তারপর সময়-অনুযায়ী prefix sum-এর max।
- **Tree path (এই folder-এর target):** একটা **range-update + range-max segment tree with lazy propagation**, time-values compress করে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এটা plain prefix sums-এ আটকায় না, কারণ event-গুলো dynamically আসছে আর প্রতিবার max লাগছে — frozen array নয়। আবার এটা range *update* (একটা পুরো interval-এ +1) + *max* query — যেখানে Fenwick স্বাভাবিকভাবে চলে না ([../fenwick-tree.md](../fenwick-tree.md) section 8: range update + max = segment tree)।
Lazy-propagation segment tree ঠিক এই "interval-এ যোগ করো, সর্বোচ্চ track করো" জোড়ার জন্য বানানো — তাই এই problem এই topic-এর lazy-propagation teaser হিসেবে নিখুঁত।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা booking-এর পর, এ পর্যন্ত আসা সব interval-কে দুটো `(time, delta)` ঘটনায় ভাঙো, সব ঘটনা sort করো, prefix sum চালিয়ে max বের করো।
```text
on each book(s, e):
events += [(s, +1), (e, -1)]
sort events by time (e আগে -1, একই time-এ)
running = 0; best = 0
for (_, d) in events: running += d; best = max(best, running)
return best
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা booking-এ এ পর্যন্ত আসা সব event আবার sort করা হয় — `k`-তম booking-এ O(k log k)। `n`-টা booking মিলিয়ে **O(n² log n)**। `n` বড় হলে ধীর। উত্তর: difference-array-টা একবার maintain করো (re-sort না করে), অথবা lazy segment tree-তে প্রতি booking O(log n)।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **একটা পুরো interval-এ "+1" করা = শুধু দুই প্রান্তে +1/−1 লেখা**। আর কোনো বিন্দুর চলমান overlap = ওই বিন্দু পর্যন্ত delta-গুলোর prefix sum। তাই max overlap = এই sweep-এর সর্বোচ্চ prefix sum — পুরো timeline না ঘেঁটে শুধু boundary-গুলো গুনলেই চলে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
একটা sorted map-এ delta জমাও: প্রতিটা `book(s, e)`-এ `delta[s] += 1`, `delta[e] -= 1`। তারপর key-গুলো সময়-অনুযায়ী হেঁটে running sum-এর max-ই উত্তর।
Tree version: time-values compress করে একটা lazy segment tree-তে `[s, e)`-এ range `+1` করো (পুরো-cover node-এ sticky note), আর root-এর global max return করো — প্রতি booking O(log n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা মুহূর্তে কতগুলো event চলছে আলাদা করে গুনব" ভাবার বদলে ভাবো "প্রতিটা interval শুধু দুটো boundary-ঘটনা; চলমান গোনা মানে boundary-গুলোর prefix sum।" একটা continuous overlap-হিসাব কয়েকটা +1/−1 marker-এ গুটিয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
বুক করা intervals আর তাদের +1/−1 sweep:
```text
events: [10,20) [50,60) [10,40) [5,15)
time-axis-এ delta sticker:
5: +1 10: +1, +1 15: -1 20: -1
40: -1 50: +1 60: -1
সময়-অনুযায়ী সাজিয়ে running sum (prefix):
t=5 : +1 -> running 1
t=10 : +1 +1 -> running 3 <- max এখানে
t=15 : -1 -> running 2
t=20 : -1 -> running 1
t=40 : -1 -> running 0
t=50 : +1 -> running 1
t=60 : -1 -> running 0
সর্বোচ্চ running = 3
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
booking ক্রম `[10,20), [50,60), [10,40)`:
1. `[10,20)`: delta `{10:+1, 20:-1}`। sweep: t10→1, t20→0। max = **1**।
2. `[50,60)`: delta `{10:+1, 20:-1, 50:+1, 60:-1}`। sweep: t10→1, t20→0, t50→1, t60→0। max = **1**।
3. `[10,40)`: delta `{10:+2, 20:-1, 40:-1, 50:+1, 60:-1}`। sweep: t10→2, t20→1, t40→0, t50→1, t60→0। max = **2**।
প্রতি step-এর শেষে return: 1, 1, 2। ✓
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class MyCalendarThree:
"""Sweep line: প্রতিটা interval [s, e)-কে delta[s] += 1, delta[e] -= 1 করে
জমাই; কোনো মুহূর্তের overlap = ওই বিন্দু পর্যন্ত prefix sum; উত্তর = max prefix।
এটাই 'interval-এ +1, global max' — যেটা lazy-propagation segment tree-রও কাজ
(`../segment-tree.md` section 9-এর teaser)। এখানে clean sorted-map রূপ।"""
def __init__(self):
self.delta = {} # time-point -> net change
def book(self, start, end):
self.delta[start] = self.delta.get(start, 0) + 1 # interval শুরু
self.delta[end] = self.delta.get(end, 0) - 1 # interval শেষ
running = 0
best = 0
for t in sorted(self.delta): # সময়-অনুযায়ী sweep
running += self.delta[t]
best = max(best, running)
return best
def brute(intervals):
# obviously-correct reference: প্রতিটা booking-এর পরের max overlap
# ছোট integer coordinate-এ unit cell গুনে (half-open [s, e))
out = []
seen = []
for s, e in intervals:
seen.append((s, e))
lo = min(a for a, _ in seen)
hi = max(b for _, b in seen)
best = 0
for t in range(lo, hi): # প্রতিটা unit time-slot [t, t+1)
cnt = sum(1 for a, b in seen if a <= t < b)
best = max(best, cnt)
out.append(best)
return out
# ---- tests ----
cal = MyCalendarThree()
assert cal.book(10, 20) == 1
assert cal.book(50, 60) == 1
assert cal.book(10, 40) == 2
assert cal.book(5, 15) == 3
assert cal.book(5, 10) == 3
assert cal.book(25, 55) == 3
# half-open: পাশাপাশি interval overlap করে না
cal2 = MyCalendarThree()
assert cal2.book(0, 10) == 1
assert cal2.book(10, 20) == 1 # 10 ছোঁয় না, তাই max এখনো 1
assert cal2.book(5, 15) == 2 # [5,15) দুটোর সাথেই 2-overlap তৈরি করে
# হুবহু একই slot বারবার -> overlap বাড়তেই থাকে
cal3 = MyCalendarThree()
assert cal3.book(1, 2) == 1
assert cal3.book(1, 2) == 2 # একই slot, দুটো একসাথে
# random fuzz: sweep-map vs unit-cell brute (ছোট coordinate)
import random
random.seed(17)
for _ in range(400):
cal_f = MyCalendarThree()
ivs = []
for _ in range(random.randint(1, 8)):
a = random.randint(0, 10)
b = random.randint(a + 1, 11) # half-open, e > s
ivs.append((a, b))
expected = brute(ivs)
got = [cal_f.book(s, e) for s, e in ivs]
assert got == expected, (ivs, got, expected)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.delta` — time-point → net change map; sweep-line-এর difference array।
- `book(start, end)` — `start`-এ `+1` (event শুরু), `end`-এ `−1` (event শেষ); half-open তাই `end` ছোঁয় না।
- `for t in sorted(self.delta)` — সময়-অনুযায়ী prefix sum চালাই; `best` ধরে রাখে সর্বোচ্চ চলমান overlap।
- `brute` — ছোট integer coordinate-এ প্রতিটা unit slot `[t, t+1)` গুনে max বের করা reference।
- random fuzz — sweep-map-এর উত্তর unit-cell brute-এর সাথে 400 case-এ মেলায়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রতিটা `book`-এর পর sweep পুরো delta map হেঁটে max overlap দেয়: `[10,20)`→1, `[50,60)`→1 (আলাদা সময়), `[10,40)`→2 (10..20 overlap), `[5,15)`→3 (10..15-এ তিনটা)। পরের দুটো আর 3 ছাড়ায় না। half-open আর "হুবহু একই slot দুবার" case-ও সঠিক, আর 400 random fuzz unit-cell brute-এর সাথে মেলে। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
এই sweep-map version: প্রতিটা `book`-এ পুরো map sort করে হাঁটা — `k`-তম call-এ O(k log k), `n` call-এ **O(n² log n)**। Lazy-propagation segment tree (compressed times) version প্রতি booking **O(log n)**, মোট **O(n log n)** — এটাই scalable target।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — delta map-এ সর্বোচ্চ `2n`-টা distinct time-point (প্রতিটা booking দুটো boundary যোগ করে)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- half-open `[s, e)`-কে closed `[s, e]` ভাবা — তাহলে পাশাপাশি interval ভুল করে overlap গোনা হয়; `end`-এ `−1` ঠিক `end`-এই, পরে নয়।
- একই time-point-এ আগের delta overwrite করা (`= 1` লেখা) `+=`-এর বদলে — একাধিক event একই বিন্দুতে শুরু হলে গোনা হারায়।
- Tree path-এ time compress না করে raw 10^9 coordinate-এ tree বানাতে চাওয়া — memory blow-up; আগে compress করো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: difference-array / sweep line ([../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/](../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/README.md)-এর interval-এ +1 trick) + segment-on-values with lazy propagation ([../segment-tree.md](../segment-tree.md) section 9 teaser)। base tree code [../implementation.py](../implementation.py)-তে।
### পরের অনুশীলন {#22-similar-harder-problems}
- My Calendar I / II (overlap সীমাবদ্ধ রাখা) —