Problem link ও উৎস
- **Original source:** Classic interview problem (railway platform)
- **Platform:** Classic interview problem — `—`
- **Topic:** Greedy math tricks → event sweep (sweep line / prefix idea)
- **Difficulty:** Medium
- **Pattern:** event sweep (arrival +1, departure −1, চলন্ত যোগফলের max)
- **Basic idea inherited from:** 080 — (level 5-এর sweep line / prefix)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা রেলস্টেশনে দিনভর কিছু ট্রেন আসে ও যায়। প্রতিটা ট্রেনের একটা **arrival time** আর একটা **departure time** দেওয়া। একটা ট্রেন স্টেশনে থাকা অবস্থায় একটা platform দখল করে রাখে।
প্রশ্ন: যাতে কোনো ট্রেনকে কখনো অপেক্ষা করতে না হয়, তার জন্য **সর্বনিম্ন কয়টা platform** দরকার?
মূল অন্তর্দৃষ্টি: উত্তর = **এক মুহূর্তে একসাথে স্টেশনে থাকা সর্বোচ্চ ট্রেন সংখ্যা**।
### Input ও output {#6-example-input-and-output}
```text
arrivals departures -> output (ব্যাখ্যা)
-------------------------------------------------------------------
[900,940,950] [910,1200,1120] -> 2 (950-এ 2টা একসাথে)
[900,1100,1235] [1000,1200,1240] -> 1 (কখনো overlap নেই)
[100] [200] -> 1 (একটাই ট্রেন)
[100,100,100] [200,200,200] -> 3 (তিনটাই একসাথে)
[] [] -> 0 (কোনো ট্রেন নেই)
```
খেয়াল করো `[100,100,100]/[200,200,200]`-এ তিনটা ট্রেনই একই সময়ে স্টেশনে — তাই 3টা platform; আর দ্বিতীয় row-তে কখনো overlap নেই বলে 1টাই যথেষ্ট।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা পার্কিং লট — গাড়ি ঢোকে, কিছুক্ষণ থাকে, বেরিয়ে যায়। তুমি জানতে চাও **সর্বোচ্চ কয়টা গাড়ি একসাথে ভেতরে ছিল**, কারণ ততগুলো পার্কিং স্পেস তোমার অন্তত লাগবেই।
প্রতিটা গাড়ি ঢোকা = ভেতরের গণনা +1, বেরোনো = −1। সারাদিনের সব ঢোকা-বেরোনোর ঘটনা সময় ধরে সাজিয়ে গুনলে গণনাটা ওঠানামা করবে; তার সর্বোচ্চ চূড়াই বলে দেবে ব্যস্ততম মুহূর্তে কয়টা স্পেস দরকার ছিল। ট্রেন-platform-ও ঠিক তাই — ব্যস্ততম মুহূর্তের চাপটাই সব ঠিক করে দেয়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
সরাসরি 080 (level 5-এর sweep line / prefix idea)-এর কাঁধে দাঁড়ানো — তাই tracker-এ "inherits from: 080"।
Level 5-এ শিখেছিলে: ঘটনাগুলোকে সময় ধরে সাজিয়ে একটা চলন্ত counter-এ +/− করে যেকোনো মুহূর্তের অবস্থা বের করা। এখানে সেই counter-ই "এই মুহূর্তে কয়টা ট্রেন স্টেশনে", আর আমরা শুধু তার সর্বোচ্চ মান খুঁজছি। নতুন কিছু নয় — পুরোনো tool নতুন মোড়কে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **event sweep (চলন্ত যোগফল)**। সময়রেখায় প্রতিটা arrival একটা `+1` ঘটনা (একটা ট্রেন ঢুকল, platform লাগল), আর প্রতিটা departure একটা `−1` ঘটনা (একটা ট্রেন গেল, platform ছাড়ল)।
সব ঘটনাকে সময় অনুযায়ী sort করে বাঁ থেকে ডানে চলন্ত যোগফল (running sum) রাখো; সেই যোগফল যত উঁচুতে ওঠে, ততগুলো ট্রেন একসাথে স্টেশনে — তার **maximum**-ই minimum platform। এটা হুবহু level 5-এর prefix-sum / sweep line idea।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি, কিন্তু ধীর চিন্তা — **প্রতিটা সম্ভাব্য সময়-বিন্দুতে গুনে দেখো কয়টা ট্রেন তখন স্টেশনে**, আর সর্বোচ্চটা রাখো। যেহেতু overlap শুধু কোনো arrival-এর মুহূর্তেই সর্বোচ্চ হতে পারে, প্রতিটা arrival সময়ে গুনলেই হয়:
```python
def min_platforms_brute(arrivals, departures):
best = 0
for t in arrivals: # প্রতিটা arrival মুহূর্তে
present = 0
for a, d in zip(arrivals, departures):
if a <= t <= d: # সেই ট্রেন তখন স্টেশনে?
present += 1
best = max(best, present)
return best
```
প্রতিটা arrival-মুহূর্তে সরাসরি গুনে দেখে, তাই উত্তর সঠিক — আমাদের যাচাইয়ের মাপকাঠি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
প্রতিটা arrival-এর জন্য আবার সব ট্রেন ঘুরে গোনা — দুই nested loop, মোট **O(n²)**। n যদি 10⁵ হয়, প্রায় 10¹⁰ operation — Time Limit Exceeded।
```text
প্রতিটা arrival-এ পুরো তালিকা আবার গোনা মানে একই কাজ বারবার।
brute force : O(n²) (ধীর)
event sweep : O(n log n) (sort + এক pass — চলন্ত যোগফল)
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation: **প্রতিটা ঘটনা শুধু একবার ঘটে — arrival +1, departure −1।** সব ঘটনা একসাথে sort করে এক pass-এ চলন্ত যোগফলের max নাও:
```python
def min_platforms(arrivals, departures):
events = [(t, 1) for t in arrivals] + [(t, -1) for t in departures]
events.sort() # সমান সময়ে −1 আগে (tuple sort ফ্রি-তে দেয়)
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
```
**Greedy/সুইপ choice:** সময় বাড়ার ক্রমে ঘটনা প্রক্রিয়া করো; চলন্ত যোগফলই বর্তমান চাপ, তার সর্বোচ্চটাই উত্তর।
**কেন কাজ করে (এক লাইন):** যেকোনো মুহূর্তে "স্টেশনে কতগুলো ট্রেন" = সেই মুহূর্ত পর্যন্ত (arrival সংখ্যা − departure সংখ্যা), যা ঠিক ঘটনাগুলোর চলন্ত যোগফল; তাই সব ঘটনা সময়-ক্রমে সাজিয়ে এই যোগফলের সর্বোচ্চ মানই সর্বোচ্চ একসাথে-থাকা ট্রেন, অর্থাৎ minimum platform।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা!":
> "ট্রেন বা interval না ভেবে আলাদা আলাদা **ঘটনা** ভাবো — arrival +1, departure −1; সময় ধরে যোগ করতে থাকলে সর্বোচ্চ চূড়াই উত্তর।"
আর সূক্ষ্ম tweak: সমান সময়ে departure-কে arrival-এর আগে রাখা — `(t, delta)` tuple sort করলে `−1 < +1` বলে এটা আপনাআপনি হয়। এই দুটো একসাথেই O(n²) brute-কে O(n log n) sweep-এ নামায়।
### ছবিতে বোঝা {#5-visual-explanation}
arrivals `[900, 940, 950]`, departures `[910, 1200, 1120]` — event sweep:
```text
সব event সময় ধরে sort (সমান সময়ে departure −1 আগে):
(900,+1) (910,−1) (940,+1) (950,+1) (1120,−1) (1200,−1)
চলন্ত যোগফল:
900 : +1 → 1
910 : −1 → 0
940 : +1 → 1
950 : +1 → 2 ← সর্বোচ্চ
1120 : −1 → 1
1200 : −1 → 0
best = 2 → 2টা platform যথেষ্ট
```
কেন সমান সময়ে departure আগে — সেই edge case:
```text
ট্রেন A: 950 departs, ট্রেন B: 950 arrives
যদি A আগে বেরোয় (−1 আগে), B তার platform-টাই পায় → বাড়তি লাগে না।
tuple sort (t, delta)-এ −1 < +1, তাই একই t-তে departure আপনাআপনি আগে আসে — ফ্রি!
(Problem-এর নিয়ম "একই সময়ে দুজনের আলাদা platform লাগবে" হলে +1 আগে আনতে হবে।)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
arrivals `[900, 940, 950]`, departures `[910, 1200, 1120]` ধীরে চালাই।
Events sort করার পর: `(900,1) (910,-1) (940,1) (950,1) (1120,-1) (1200,-1)`
| event (t, delta) | cur += delta | best = max(best, cur) |
| --- | --- | --- |
| শুরু | 0 | 0 |
| (900, +1) | 1 | 1 |
| (910, −1) | 0 | 1 |
| (940, +1) | 1 | 1 |
| (950, +1) | 2 | **2** |
| (1120, −1) | 1 | 2 |
| (1200, −1) | 0 | 2 |
`best = 2` → 2টা platform। লক্ষ করো 950-এ দুটো ট্রেন একসাথে থাকায় সেখানেই চূড়া উঠল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def min_platforms(arrivals, departures):
"""event sweep: arrival +1, departure −1; চলন্ত যোগফলের max।"""
events = [(t, 1) for t in arrivals] + [(t, -1) for t in departures]
events.sort() # সমান সময়ে departure (−1) আগে
cur = best = 0
for _, delta in events:
cur += delta
best = max(best, cur)
return best
def min_platforms_brute(arrivals, departures):
"""প্রতিটা arrival মুহূর্তে গুনে দেখা — O(n²), নির্ভুল (যাচাই)।
departure মুহূর্তে platform ছেড়ে দেওয়া হয় (sweep-এর মতো), তাই a <= t < d।"""
best = 0
for t in arrivals:
present = 0
for a, d in zip(arrivals, departures):
if a <= t < d:
present += 1
best = max(best, present)
return best
# --- ছোট test (সব pass করা উচিত) ---
assert min_platforms([900, 940, 950], [910, 1200, 1120]) == 2
assert min_platforms([900, 1100, 1235], [1000, 1200, 1240]) == 1
assert min_platforms([100], [200]) == 1
assert min_platforms([100, 100, 100], [200, 200, 200]) == 3
assert min_platforms([], []) == 0
# event sweep আর brute force ছোট সব case-এ একমত (brute = সত্য)
import random
random.seed(1)
for _ in range(500):
n = random.randint(1, 7)
arr, dep = [], []
for _ in range(n):
a = random.randint(0, 10)
d = random.randint(a, a + 10) # departure ≥ arrival
arr.append(a)
dep.append(d)
assert min_platforms(arr, dep) == min_platforms_brute(arr, dep)
print(min_platforms([900, 940, 950], [910, 1200, 1120])) # 2
print(min_platforms([900, 1100, 1235], [1000, 1200, 1240])) # 1
print(min_platforms([100, 100, 100], [200, 200, 200])) # 3
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
events = [(t, 1) for t in arrivals] + [(t, -1) for t in departures]
```
প্রতিটা arrival-কে `+1` ঘটনা, প্রতিটা departure-কে `−1` ঘটনা বানাই — interval ভেঙে আলাদা আলাদা ঘটনায়।
```text
events.sort()
```
`(t, delta)` tuple sort: আগে সময় `t` ধরে, সমান হলে `delta` ধরে (−1 < +1) — তাই একই মুহূর্তে departure আগে প্রক্রিয়া হয়, যা এই problem-এর সঠিক নিয়ম।
```text
cur += delta
best = max(best, cur)
```
`cur` = এই মুহূর্তে স্টেশনে কয়টা ট্রেন (চলন্ত যোগফল); প্রতিবার আপডেট করে তার সর্বোচ্চ মান `best`-এ রাখি — সেটাই minimum platform।
`min_platforms_brute` প্রতিটা arrival-মুহূর্তে সরাসরি গুনে নির্ভুল উত্তর দেয়; random ছোট schedule বানিয়ে (departure ≥ arrival নিশ্চিত করে) sweep আর brute মিলিয়ে দেখা হয়েছে।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
2
1
3
সব test pass!
```
প্রথম তিন line `print` থেকে: প্রথম schedule-এ 2টা platform, দ্বিতীয়টায় কখনো overlap না থাকায় 1টা, তৃতীয়টায় তিন ট্রেন একসাথে বলে 3টা। তার আগে সব `assert` (সরাসরি case + 500টা random schedule) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log n)** — মূল খরচ 2n টা ঘটনা sort করা; তারপর এক pass O(n)। brute force-এর O(n²) থেকে বড় উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** — 2n টা ঘটনার একটা তালিকা বানাতে হয়। (চাইলে arrivals ও departures আলাদা sort করে দুই-pointer দিয়েও O(1) বাড়তি জায়গায় করা যায়।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **একই সময়ের arrival/departure-এর ক্রম ভুল করা** — সমান সময়ে departure আগে না হলে (এই নিয়মে) ভুলভাবে একটা বাড়তি platform গোনা হবে; tuple sort এটা ঠিক রাখে, কিন্তু নিয়ম উল্টো হলে `+1` আগে আনতে হবে।
- **arrivals আর departures আলাদাভাবে sort করে index মিলিয়ে ফেলা** — দুই array আলাদা sort করলে কোন departure কোন arrival-এর তা হারিয়ে যায়; দুই-pointer পদ্ধতিতে এটা ঠিক থাকে, কিন্তু সাবধানে।
- **interval হিসেবে গুনতে গিয়ে O(n²)-এ আটকে যাওয়া** — প্রতিটা মুহূর্তে সব ট্রেন গোনা slow; event sweep-ই দ্রুত পথ।
- **departure-এর মুহূর্তে platform এখনো দখল ধরা** — এই নিয়মে departure মানে platform ছেড়ে দেওয়া; `≤` বনাম `<` সীমানা problem-এর সংজ্ঞা মেনে ঠিক করো।
- **খালি schedule না সামলানো** — কোনো ট্রেন না থাকলে উত্তর 0; loop এমনিতেই সামলায়, তবু খেয়াল রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Meeting Rooms II** (