108 — Minimum Platforms¶

Level 5-এর সেই sweep line মনে আছে? সে ফিরে এসেছে! এই problem-এ arrival = +1, departure = −1 — সময় ধরে চলন্ত যোগফলের সর্বোচ্চটাই উত্তর। পুরোনো বন্ধুর সাথে পুনর্মিলন, আর সাথে একটা classic edge case (একই সময়ে আসা-যাওয়া)। ধীরে পড়ো, +1/−1-এর ছন্দটা ধরো।

Source¶

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)

1. Problem in simple words¶

একটা রেলস্টেশনে দিনভর কিছু ট্রেন আসে ও যায়। প্রতিটা ট্রেনের একটা arrival time আর একটা departure time দেওয়া। একটা ট্রেন স্টেশনে থাকা অবস্থায় একটা platform দখল করে রাখে।

প্রশ্ন: যাতে কোনো ট্রেনকে কখনো অপেক্ষা করতে না হয়, তার জন্য সর্বনিম্ন কয়টা platform দরকার?

মূল অন্তর্দৃষ্টি: উত্তর = এক মুহূর্তে একসাথে স্টেশনে থাকা সর্বোচ্চ ট্রেন সংখ্যা।

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।

3. Which basic idea does this inherit from?¶

সরাসরি 080 (level 5-এর sweep line / prefix idea)-এর কাঁধে দাঁড়ানো — তাই tracker-এ "inherits from: 080"।

Level 5-এ শিখেছিলে: ঘটনাগুলোকে সময় ধরে সাজিয়ে একটা চলন্ত counter-এ +/− করে যেকোনো মুহূর্তের অবস্থা বের করা। এখানে সেই counter-ই "এই মুহূর্তে কয়টা ট্রেন স্টেশনে", আর আমরা শুধু তার সর্বোচ্চ মান খুঁজছি। নতুন কিছু নয় — পুরোনো tool নতুন মোড়কে।

4. Real-life analogy¶

ভাবো একটা পার্কিং লট — গাড়ি ঢোকে, কিছুক্ষণ থাকে, বেরিয়ে যায়। তুমি জানতে চাও সর্বোচ্চ কয়টা গাড়ি একসাথে ভেতরে ছিল, কারণ ততগুলো পার্কিং স্পেস তোমার অন্তত লাগবেই।

প্রতিটা গাড়ি ঢোকা = ভেতরের গণনা +1, বেরোনো = −1। সারাদিনের সব ঢোকা-বেরোনোর ঘটনা সময় ধরে সাজিয়ে গুনলে গণনাটা ওঠানামা করবে; তার সর্বোচ্চ চূড়াই বলে দেবে ব্যস্ততম মুহূর্তে কয়টা স্পেস দরকার ছিল। ট্রেন-platform-ও ঠিক তাই — ব্যস্ততম মুহূর্তের চাপটাই সব ঠিক করে দেয়।

5. Visual explanation¶

arrivals [900, 940, 950], departures [910, 1200, 1120] — event sweep:

সব 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:

ট্রেন A: 950 departs,  ট্রেন B: 950 arrives
যদি A আগে বেরোয় (−1 আগে), B তার platform-টাই পায় → বাড়তি লাগে না।

tuple sort (t, delta)-এ −1 < +1, তাই একই t-তে departure আপনাআপনি আগে আসে — ফ্রি!
(Problem-এর নিয়ম "একই সময়ে দুজনের আলাদা platform লাগবে" হলে +1 আগে আনতে হবে।)

6. Example input and output¶

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টাই যথেষ্ট।

7. Brute force thinking¶

সরাসরি, কিন্তু ধীর চিন্তা — প্রতিটা সম্ভাব্য সময়-বিন্দুতে গুনে দেখো কয়টা ট্রেন তখন স্টেশনে, আর সর্বোচ্চটা রাখো। যেহেতু overlap শুধু কোনো arrival-এর মুহূর্তেই সর্বোচ্চ হতে পারে, প্রতিটা arrival সময়ে গুনলেই হয়:

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।

প্রতিটা arrival-এ পুরো তালিকা আবার গোনা মানে একই কাজ বারবার।

brute force : O(n²)        (ধীর)
event sweep : O(n log n)   (sort + এক pass — চলন্ত যোগফল)

9. Better thinking¶

মূল observation: প্রতিটা ঘটনা শুধু একবার ঘটে — arrival +1, departure −1। সব ঘটনা একসাথে sort করে এক pass-এ চলন্ত যোগফলের max নাও:

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-এ নামায়।

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-এ দুটো ট্রেন একসাথে থাকায় সেখানেই চূড়া উঠল।

12. Python solution¶

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¶

events = [(t, 1) for t in arrivals] + [(t, -1) for t in departures]

প্রতিটা arrival-কে +1 ঘটনা, প্রতিটা departure-কে −1 ঘটনা বানাই — interval ভেঙে আলাদা আলাদা ঘটনায়।

events.sort()

(t, delta) tuple sort: আগে সময় t ধরে, সমান হলে delta ধরে (−1 < +1) — তাই একই মুহূর্তে departure আগে প্রক্রিয়া হয়, যা এই problem-এর সঠিক নিয়ম।

cur += delta
best = max(best, cur)

cur = এই মুহূর্তে স্টেশনে কয়টা ট্রেন (চলন্ত যোগফল); প্রতিবার আপডেট করে তার সর্বোচ্চ মান best-এ রাখি — সেটাই minimum platform।

min_platforms_brute প্রতিটা arrival-মুহূর্তে সরাসরি গুনে নির্ভুল উত্তর দেয়; random ছোট schedule বানিয়ে (departure ≥ arrival নিশ্চিত করে) sweep আর brute মিলিয়ে দেখা হয়েছে।

14. Output walkthrough¶

চালালে ছাপবে:

2
1
3
সব test pass!

প্রথম তিন line print থেকে: প্রথম schedule-এ 2টা platform, দ্বিতীয়টায় কখনো overlap না থাকায় 1টা, তৃতীয়টায় তিন ট্রেন একসাথে বলে 3টা। তার আগে সব assert (সরাসরি case + 500টা random schedule) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

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 এমনিতেই সামলায়, তবু খেয়াল রাখো।

18. Harder problems that inherit this idea¶

LeetCode — Meeting Rooms II (https://leetcode.com/problems/meeting-rooms-ii/) — হুবহু একই problem (সর্বনিম্ন meeting room = সর্বোচ্চ overlap), event sweep বা min-heap দিয়ে।
LeetCode — Car Pooling (https://leetcode.com/problems/car-pooling/) — +passengers / −passengers ঘটনা, চলন্ত যোগফল capacity ছাড়ায় কিনা।
LeetCode — My Calendar II / III (https://leetcode.com/problems/my-calendar-iii/) — interval-এর সর্বোচ্চ overlap track করার আরও সাধারণ রূপ।

19. Pattern learned¶

Event sweep (sweep line, +1/−1 running sum) — interval-কে আলাদা arrival(+1)/departure(−1) ঘটনায় ভাঙো, সময় ধরে sort করে চলন্ত যোগফলের সর্বোচ্চ নাও। বড় শিক্ষা: "এক মুহূর্তে কয়জন একসাথে" ধরনের প্রশ্নে ঘটনায় ভেঙে চলন্ত যোগফল ভাবো — level 5-এর sweep line-ই উত্তর।

20. Final summary¶

ভবিষ্যতের আমাকে এক লাইনে: "Minimum platforms = event sweep; arrival +1, departure −1, (t, delta) sort করে চলন্ত যোগফলের max। সমান সময়ে departure আগে — tuple sort ফ্রি-তে দেয়। এটা level 5-এর sweep line-এরই পুনর্জন্ম।"

পরের ধাপ → 109 — Rearrange with Constraints (frequency greedy — সবচেয়ে বড় হুমকি আগে নামাও)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

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