Problem link ও উৎস
- **Original source:** Classic interval scheduling
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Scheduling by earliest end
- **Basic idea inherited from:** `02-arrays-and-strings` interval sorting — start দিয়ে sort, তারপর end times-এর min-heap
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো meeting দেওয়া আছে, প্রতিটার একটা `[start, end]`। একটা ঘরে একসাথে একটাই meeting হতে পারে। তোমাকে বলতে হবে সব meeting আঁটাতে **সবচেয়ে কম কতগুলো ঘর** লাগবে। অর্থাৎ কোনো এক মুহূর্তে সর্বোচ্চ কয়টা meeting একসাথে overlap করে, সেই সংখ্যাটা।
```text
meetings = [[0, 30], [5, 10], [15, 20]] -> 2টা ঘর লাগবে
```
### Input ও output {#8-example-input-and-output}
```text
Input : meetings = [[0,30],[5,10],[15,20]] -> Output: 2
Input : meetings = [[7,10],[2,4]] -> Output: 1 (overlap নেই)
Input : meetings = [[1,5],[2,6],[3,7]] -> Output: 3 (তিনটাই overlap)
Input : meetings = [] -> Output: 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা office-এ receptionist মিটিং রুম বরাদ্দ করছেন। তিনি একটা তালিকা রাখেন কোন রুম কখন খালি হবে, আর সবচেয়ে আগে খালি-হওয়া রুমটা সামনে (min-heap top)। নতুন মিটিং এলে তিনি শুধু সেই সবচেয়ে-আগে-খালি রুমটা দেখেন — সময় হয়ে গেলে সেটা reuse, নাহলে নতুন রুম খোলেন। সেই "সবচেয়ে আগে খালি-হওয়া রুম দাও" যন্ত্রটাই end-times min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত হলো `02-arrays-and-strings`-এর **interval sorting** — meeting-গুলোকে start time দিয়ে সাজানো। তারপর `08`-এর heap: চলমান meeting-গুলোর **end time**-এর একটা min-heap রাখা, যাতে "এখনকার কোন meeting সবার আগে শেষ হবে" তাৎক্ষণিক জানা যায়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: **লাগবে এমন ঘরের সংখ্যা = কোনো মুহূর্তে সর্বোচ্চ concurrent meeting**। meeting-গুলো start order-এ process করলে, নতুন meeting শুরুর সময় যত meeting এখনো চলছে (অর্থাৎ end > এই start), তাদের সবার আলাদা ঘর লাগবে। এই overlap-এর peak-ই উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap of end times**। heapq সরাসরি min-heap, আর আমরা চাই top-এ থাকুক চলমান meeting-দের মধ্যে সবচেয়ে আগে শেষ-হওয়াটা — তাই plain min-heap যথেষ্ট, negate লাগে না। (সাথে শুরুতে start দিয়ে একটা sort।)
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
নতুন meeting শুরু হলে একটাই প্রশ্ন: "কোনো ঘর কি এর start-এর মধ্যে খালি হয়েছে?" — অর্থাৎ চলমান meeting-দের মধ্যে সবচেয়ে আগে শেষ-হওয়াটা কি এই start-এর আগে শেষ? সেই earliest end হলো min-heap top, O(1)-এ পাওয়া যায়। সব ঘর scan করতে হয় না। প্রতিটা meeting-এ বড়জোর একটা push আর একটা pop — O(log n)।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য time point-এ গুনে দেখো কয়টা meeting active — সব meeting-এর সব time চেক করে maximum overlap বের করো।
```text
প্রতিটা meeting-এর জন্য বাকি সব meeting দেখো overlap করে কিনা -> peak গোনো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা meeting অন্য সবার সাথে overlap চেক করা মানে **O(n²)** (বা time points নিয়ে আরও বেশি)। অথচ start order-এ একবার হেঁটে গিয়ে একটা end-time heap রাখলেই peak overlap সরাসরি বেরিয়ে আসে — সব জোড়া মেলানো নিখাদ অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: meeting-গুলো **start order-এ** process করলে, নতুন meeting-এর জন্য সম্ভাব্য একটাই খালি ঘর হতে পারে — যেটা **সবার আগে শেষ হয়**। সেই earliest end যদি নতুন start-এর `<=` হয়, ঘর reuse; নাহলে নতুন ঘর। heap top-ই সেই earliest end।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
start দিয়ে sort করো। একটা min-heap রাখো চলমান end times-এর। প্রতিটা meeting `[s, e]`-এর জন্য: heap top `<= s` হলে pop (ঘর free হলো), তারপর `e` push। heap-এর সর্বোচ্চ size-ই লাগবে এমন ঘরের সংখ্যা। sort O(n log n), প্রতিটা meeting O(log n) — মোট O(n log n)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কয়টা ঘর লাগবে" না ভেবে ভাবো "কোনো মুহূর্তে সর্বোচ্চ কয়টা meeting একসাথে চলছে।" আর সেই concurrency track করার চাবি একটাই প্রশ্ন — "চলমানদের মধ্যে কে সবার আগে শেষ হবে?" — যা min-heap O(1)-এ বলে। যেকোনো "minimum rooms/platforms/machines" এই earliest-end ছাঁচে পড়ে।
### ছবিতে বোঝা {#7-visual-explanation}
`meetings = [[0,30],[5,10],[15,20]]`। start দিয়ে sort (এখানে already sorted)। min-heap রাখে চলমান end times:
```text
sort by start: (0,30) (5,10) (15,20)
(0,30): heap খালি -> নতুন ঘর -> heap of ends [30] ঘর = 1
(5,10): earliest end 30 > 5 -> reuse করা যায় না -> নতুন ঘর
-> heap [10, 30] ঘর = 2
(15,20): earliest end 10 <= 15 -> ঘরটা খালি! pop 10
-> push 20 -> heap [20, 30] ঘর = 2 (unchanged)
সর্বোচ্চ heap size = 2 -> উত্তর 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `meetings = [[0,30],[5,10],[15,20]]`:
1. start দিয়ে sort → [[0,30],[5,10],[15,20]] (already)
2. [0,30]: heap খালি → push 30 → heap {30}, ঘর = 1
3. [5,10]: top 30 `<= 5`? না → reuse নেই → push 10 → heap {10,30}, ঘর = 2
4. [15,20]: top 10 `<= 15`? হ্যাঁ → pop 10 (ঘর free) → push 20 → heap {20,30}, size 2
5. সর্বোচ্চ size = 2 → return 2
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def min_meeting_rooms(meetings):
if not meetings:
return 0
meetings.sort(key=lambda m: m[0]) # start time দিয়ে sort
ends = [] # min-heap of চলমান end times
rooms = 0
for start, end in meetings:
if ends and ends[0] <= start: # সবচেয়ে আগে শেষ-হওয়া ঘর খালি?
heapq.heappop(ends) # সেই ঘর reuse করো
heapq.heappush(ends, end) # এই meeting একটা ঘর দখল করল
rooms = max(rooms, len(ends)) # peak concurrency = লাগবে এমন ঘর
return rooms
# ---- tests ----
assert min_meeting_rooms([[0, 30], [5, 10], [15, 20]]) == 2
assert min_meeting_rooms([[7, 10], [2, 4]]) == 1 # overlap নেই
assert min_meeting_rooms([[1, 5], [2, 6], [3, 7]]) == 3 # তিনটাই overlap
assert min_meeting_rooms([[1, 10]]) == 1 # একটাই
assert min_meeting_rooms([]) == 0 # কিছু নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not meetings: return 0` — কোনো meeting না থাকলে ঘর লাগে না।
- `meetings.sort(key=lambda m: m[0])` — start time দিয়ে সাজানো; ছাড়া earliest-end যুক্তি ভাঙে।
- `ends = []` — min-heap, top-এ সবচেয়ে আগে শেষ-হওয়া চলমান meeting-এর end।
- `if ends and ends[0] <= start:` — সবচেয়ে আগে শেষ-হওয়া ঘর কি এই meeting শুরুর আগে খালি?
- `heapq.heappop(ends)` — খালি হলে সেই ঘর ছেড়ে দাও (reuse)।
- `heapq.heappush(ends, end)` — এই meeting একটা ঘর নেয়; heap size = এখন active ঘর।
- `rooms = max(rooms, len(ends))` — heap-এর সর্বোচ্চ size-ই peak concurrency = উত্তর।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`min_meeting_rooms([[0,30],[5,10],[15,20]])` section 14 মেনে 2 দেয় — assert pass। `[[7,10],[2,4]]` sort → [[2,4],[7,10]]; [7,10]-এর সময় top 4 ≤ 7 → reuse → max size 1। `[[1,5],[2,6],[3,7]]` কেউ আগে শেষ হয় না → size 3-এ পৌঁছায়। `[[1,10]]` → 1; `[]` → 0। পাঁচটা assert pass করার পরে print হয়: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// Node-এ built-in heap নেই; সংখ্যার একটা minimal MinHeap (top = সবচেয়ে ছোট)
class MinHeap {
constructor() { this.a = []; }
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] <= a[i]) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let s = i;
if (l < a.length && a[l] < a[s]) s = l;
if (r < a.length && a[r] < a[s]) s = r;
if (s === i) break;
[a[s], a[i]] = [a[i], a[s]]; i = s;
}
}
return top;
}
}
function minMeetingRooms(meetings) {
if (meetings.length === 0) return 0;
meetings.sort((m1, m2) => m1[0] - m2[0]); // start time দিয়ে sort
const ends = new MinHeap(); // চলমান end times-এর min-heap
let rooms = 0;
for (const [start, end] of meetings) {
if (ends.size > 0 && ends.peek() <= start) ends.pop(); // সবচেয়ে আগে শেষ-হওয়া ঘর খালি? reuse
ends.push(end); // এই meeting একটা ঘর নিল
rooms = Math.max(rooms, ends.size); // peak concurrency = লাগবে এমন ঘর
}
return rooms;
}
// ---- test cases ----
assert(minMeetingRooms([[0, 30], [5, 10], [15, 20]]) === 2, "basic");
assert(minMeetingRooms([[7, 10], [2, 4]]) === 1, "overlap নেই");
assert(minMeetingRooms([[1, 5], [2, 6], [3, 7]]) === 3, "তিনটাই overlap");
assert(minMeetingRooms([[1, 10]]) === 1, "একটাই");
assert(minMeetingRooms([]) === 0, "কিছু নেই");
console.log("সব JS test pass!");
```
> **JS টীকা:** দুটো জিনিস খেয়াল করো: (১) **JS-এ built-in heap নেই**, তাই সংখ্যার `MinHeap` হাতে লিখলাম; (২) JS-এর `sort` ডিফল্টে string-এর মতো sort করে, তাই সংখ্যার জন্য অবশ্যই comparator দিতে হয় — `(m1, m2) => m1[0] - m2[0]`, না হলে `[10]` `[5]`-এর আগে চলে আসত। `<=` (না `<`) ব্যবহার করেছি, কারণ একটা meeting শেষ হওয়ার ঠিক মুহূর্তে আরেকটা শুরু হলে ঘর reuse করা যায়।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class MinHeap {
private a: number[] = [];
get size(): number { return this.a.length; }
peek(): number { return this.a[0]; }
push(x: number): void {
const a = this.a; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (a[p] <= a[i]) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop(): number {
const a = this.a, top = a[0], last = a.pop() as number;
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let s = i;
if (l < a.length && a[l] < a[s]) s = l;
if (r < a.length && a[r] < a[s]) s = r;
if (s === i) break;
[a[s], a[i]] = [a[i], a[s]]; i = s;
}
}
return top;
}
}
function minMeetingRooms(meetings: number[][]): number {
if (meetings.length === 0) return 0;
meetings.sort((m1, m2) => m1[0] - m2[0]);
const ends = new MinHeap();
let rooms = 0;
for (const [start, end] of meetings) {
if (ends.size > 0 && ends.peek() <= start) ends.pop();
ends.push(end);
rooms = Math.max(rooms, ends.size);
}
return rooms;
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
expect(minMeetingRooms([[0, 30], [5, 10], [15, 20]]) === 2, "2");
expect(minMeetingRooms([[7, 10], [2, 4]]) === 1, "1");
expect(minMeetingRooms([[1, 5], [2, 6], [3, 7]]) === 3, "3");
expect(minMeetingRooms([[1, 10]]) === 1, "একক");
expect(minMeetingRooms([]) === 0, "খালি");
console.log("সব TS test pass!");
```
> **TS টীকা:** parameter type `number[][]` স্পষ্ট করে দেয় input হলো interval-এর array (প্রতিটা `[start, end]`)। `for (const [start, end] of meetings)`-এ destructuring-এ `start`/`end` দুটোই `number` হিসেবে infer হয়, তাই heap-এ push করা ও তুলনা type-safe। `private a: number[]` heap-এ শুধু সংখ্যা (end times) নিশ্চিত করে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log n)** — start দিয়ে sort O(n log n); তারপর প্রতিটা meeting-এ বড়জোর একটা push আর একটা pop, প্রতিটা O(log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সবচেয়ে খারাপ ক্ষেত্রে (সব meeting overlap) heap-এ n-টা end time থাকতে পারে। sort-এর জন্যও O(n) (বা in-place হলে কম)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- start দিয়ে sort না করা — তখন meeting-গুলো এলোমেলো order-এ আসে, earliest-end reuse যুক্তি ভেঙে পড়ে।
- end time-এ `<` বনাম `<=` গুলিয়ে ফেলা — একটা meeting শেষ হওয়ার ঠিক সেই মুহূর্তে আরেকটা শুরু হলে সাধারণত ঘর reuse করা যায়, তাই `<=`।
- শুধু শেষে heap size দেখা — peak ধরতে প্রতিটা step-এ `max` নিতে হবে (যদিও push-only বাড়ায় বলে শেষ size প্রায়ই peak, max নেওয়া নিরাপদ)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `02-arrays-and-strings`-এর interval sorting, আর `08`-এর Pattern 4 (`patterns.md`) — "earliest end দিয়ে scheduling"। greedy proof-টা classic activity-selection-এর সেই একই exchange argument। এটা scheduling-heap family-র প্রতিনিধি problem।
### পরের অনুশীলন {#22-similar-harder-problems}
- Single-Threaded CPU —