009 — Meeting Rooms II

Source

• Original source: Classic interval scheduling
• Platform: LeetCode — https://leetcode.com/problems/meeting-rooms-ii/
• 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

1. Problem in simple words

কতগুলো meeting দেওয়া আছে, প্রতিটার একটা [start, end]। একটা ঘরে একসাথে একটাই meeting হতে পারে। তোমাকে বলতে হবে সব meeting আঁটাতে সবচেয়ে কম কতগুলো ঘর লাগবে। অর্থাৎ কোনো এক মুহূর্তে সর্বোচ্চ কয়টা meeting একসাথে overlap করে, সেই সংখ্যাটা।

meetings = [[0, 30], [5, 10], [15, 20]]  ->  2টা ঘর লাগবে

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)।

6. Real-life analogy

একটা office-এ receptionist মিটিং রুম বরাদ্দ করছেন। তিনি একটা তালিকা রাখেন কোন রুম কখন খালি হবে, আর সবচেয়ে আগে খালি-হওয়া রুমটা সামনে (min-heap top)। নতুন মিটিং এলে তিনি শুধু সেই সবচেয়ে-আগে-খালি রুমটা দেখেন — সময় হয়ে গেলে সেটা reuse, নাহলে নতুন রুম খোলেন। সেই "সবচেয়ে আগে খালি-হওয়া রুম দাও" যন্ত্রটাই end-times min-heap।

7. Visual explanation

meetings = [[0,30],[5,10],[15,20]]। start দিয়ে sort (এখানে already sorted)। min-heap রাখে চলমান end times:

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

8. Example input and output

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

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য time point-এ গুনে দেখো কয়টা meeting active — সব meeting-এর সব time চেক করে maximum overlap বের করো।

প্রতিটা 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 ছাঁচে পড়ে।

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

15. Python solution

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 = উত্তর।

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!।

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 নেওয়া নিরাপদ)।

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 — https://leetcode.com/problems/single-threaded-cpu/ (এই tracker-এর #13)
• Car Pooling — https://leetcode.com/problems/car-pooling/
• Task Scheduler — https://leetcode.com/problems/task-scheduler/ (#10)

23. Pattern learned

Earliest-end scheduling: "minimum rooms/machines/platforms" দেখলে — start দিয়ে sort, চলমান কাজের end times-এর min-heap রাখো, নতুন কাজ এলে top <= start হলে reuse নাহলে নতুন। heap-এর peak size = উত্তর। heap একটাই প্রশ্নের উত্তর দেয়: "কে সবার আগে শেষ হবে?"

24. Final summary

ভবিষ্যতের আমাকে: "কত ঘর/মেশিন লাগবে, intervals দেওয়া" = start দিয়ে sort + end-times min-heap, peak size-ই উত্তর। মনে রেখো — প্রশ্নটা আসলে "max concurrent overlap", আর earliest-end heap সেটা সস্তায় track করে। এই scheduling reflex পরে CPU/task problem-এও কাজে দেবে।

25. JavaScript solution (with test cases)

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 করা যায়।

26. TypeScript solution (with test cases)

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) নিশ্চিত করে।

27. কোথায় কাজে লাগে (real-world use)

• Meeting room / resource booking: একসাথে সর্বোচ্চ কতগুলো overlapping booking হতে পারে — কতগুলো room/server/license লাগবে তা নির্ণয়ে।
• Concurrent connection sizing: একটা সময়ে সর্বোচ্চ কত concurrent request/connection আসে — server thread-pool বা DB connection-pool আকার ঠিক করতে।
• CPU / VM provisioning: overlapping job-গুলোর জন্য কতগুলো parallel worker/core লাগবে তা estimate করা।
• Airport gate / platform allocation: overlapping flight/train schedule-এ কতগুলো gate বা platform লাগবে।
• Bandwidth / call center staffing: একসাথে সর্বোচ্চ কত call/stream active থাকে — capacity planning-এ।

মূল সুর: "intervals দেওয়া, একসাথে সর্বোচ্চ কত overlap / কত resource লাগবে" — start দিয়ে sort করে চলমান end-times-এর min-heap রাখো, peak size-ই উত্তর।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।