079 — Imos Method Basic

069-এর difference array মনে আছে? দুই প্রান্তে দাগ দিয়ে range update। Imos method আসলে সেই জিনিসেরই আরেক নাম — শুধু দৃষ্টিটা event-ভিত্তিক। "একজন অতিথি সময় l-এ ঢোকে, r-এ বেরোয়" — timeline-এ +1 দাগ ঢোকায়, −1 দাগ বেরোয়, তারপর prefix চালিয়ে প্রতি মুহূর্তে কতজন ভেতরে। ব্যবধানকে event-এ অনুবাদ করার এই অভ্যাসটাই sweep line (080)-এর দরজা। ধীরে পড়ো।

Source

• Original source: Classic technique (imos method — interval event counting)
• Platform: Classic technique (imos method) — https://usaco.guide/silver/more-prefix-sums
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: imos method (interval → +1/−1 events → prefix)
• Basic idea inherited from: 069 — Difference Array

1. Problem in simple words

কিছু interval (অন্তর্বর্তী সময়) দেওয়া — প্রতিটা [l, r] মানে "সময় l থেকে r পর্যন্ত (দুই প্রান্ত সহ) একজন উপস্থিত"। তোমাকে বলতে হবে — প্রতিটা সময় বিন্দুতে (0 থেকে T-1) মোট কতজন একসাথে উপস্থিত?

যেমন interval [(0,2), (1,3), (4,4)], T=5 হলে প্রতিটা সময়ে উপস্থিতি: [1, 2, 2, 1, 1] — সময় 1 আর 2-এ দুজন overlap করছে। এটা imos method-এর ভিত্তি; এই count থেকে "সর্বোচ্চ একসাথে কতজন" বা "কোন সময়ে কেউ নেই"-ও সহজে বের হয়।

2. What is the math idea?

মূল idea হলো imos method — একটা interval-কে দুটো event-এ ভাঙা, তারপর prefix sum।

প্রতিটা interval [l, r] মানে: সময় l-এ একজন ঢুকল (+1), সময় r+1-এ একজন বেরোল (−1)। এটা ঠিক difference array (069):

diff[l] += 1       (ঢোকা)
diff[r + 1] -= 1   (বেরোনো)

সব interval-এর event বসিয়ে, এক pass prefix sum চালালে প্রতিটা সময়ে "ভেতরে কতজন" বেরিয়ে আসে — কারণ prefix হলো "এ পর্যন্ত মোট +1 আর −1-এর যোগফল" = এখন ভেতরে কতজন। difference নেয় event, prefix বানায় count।

3. Which basic idea does this inherit from?

সরাসরি 069 (Difference Array) থেকে — হুবহু সেই "দুই প্রান্তে দাগ, শেষে prefix" কৌশল। পার্থক্য শুধু দৃষ্টিভঙ্গিতে: 069-এ ছিল "range-এ x যোগ করো"; এখানে "interval = একজন উপস্থিত, +1"।

069-এর update ছিল arbitrary x; imos-এ x = +1 (ঢোকা) আর −1 (বেরোনো) — মানুষ গোনা। তাই imos = difference array-র event-রূপ। এই অনুবাদ — "ব্যবধান মানে দুটো প্রান্তিক ঘটনা" — পরবর্তী sweep line (080)-এর সরাসরি ভিত্তি। 069 না বুঝলে imos রহস্যময় লাগবে।

4. Real-life analogy

ভাবো একটা পার্টি হল, আর একটা গণনা-যন্ত্র দরজায়। প্রতিজন অতিথি একটা সময়ে ঢোকে আর একটা সময়ে বেরোয়।

তুমি প্রতিটা অতিথির পুরো উপস্থিত-সময় ধরে গোনার বদলে, শুধু দরজার ঘটনা লিখে রাখো: কেউ ঢুকলে "+1", বেরোলে "−1"। দিনের শেষে এই ঘটনাগুলো সময় অনুযায়ী সাজিয়ে, শুরু থেকে একটা running count রাখো — "+1 দেখলে বাড়াও, −1 দেখলে কমাও"। প্রতিটা মুহূর্তে এই count-ই বলে দেয় হলে তখন কতজন ছিল।

দরজার দুটো ঘটনা (ঢোকা, বেরোনো) দিয়ে পুরো উপস্থিতি-সময় সামলে গেল — ভেতরের প্রতিটা মুহূর্ত আলাদা গোনা লাগল না। এটাই imos: ব্যবধানকে দুটো event-এ নামানো, তারপর running total।

5. Visual explanation

interval [(0,2), (1,3), (4,4)], T=5। difference array diff (দৈর্ঘ্য T+1=6):

শুরু:            diff = [0, 0, 0, 0, 0, 0]

[0,2]: diff[0]+=1, diff[3]-=1   → [1, 0, 0, -1, 0, 0]
[1,3]: diff[1]+=1, diff[4]-=1   → [1, 1, 0, -1, -1, 0]
[4,4]: diff[4]+=1, diff[5]-=1   → [1, 1, 0, -1, 0, -1]

prefix চালিয়ে (running count = এখন কতজন ভেতরে):

time t:       0     1     2     3     4
diff[t]:      1     1     0    -1     0
running:      1  →  2  →  2  →  1  →  1
counts =    [ 1,    2,    2,    1,    1 ]

ছবিটা ধরো: time 1-এ দ্বিতীয় অতিথি ঢুকল (count 1→2), time 3-এ প্রথমজন বেরোল (count 2→1)। interval [0,2]-এর "বেরোনো" দাগ গেল diff[3]-এ (r+1=3), কারণ time 2 পর্যন্ত সে উপস্থিত। প্রতিটা +1/−1 event timeline-এ সঠিক জায়গায়।

6. Example input and output

intervals                 T   -> counts
-----------------------------------------------------
[(0,2), (1,3), (4,4)]     5   -> [1, 2, 2, 1, 1]
[(0,4)]                   5   -> [1, 1, 1, 1, 1]   (একজন সারা সময়)
[(1,1), (1,1)]            3   -> [0, 2, 0]         (দুজন একই বিন্দুতে)
[(0,0), (2,2)]            3   -> [1, 0, 1]         (মাঝে কেউ নেই)
[]                        3   -> [0, 0, 0]         (কোনো interval নেই)

সর্বোচ্চ overlap = max(counts);  উপরের প্রথমটায় = 2

Edge case: একই বিন্দুতে একাধিক ঢোকা ([(1,1),(1,1)] → time 1-এ 2) — diff স্বাভাবিকভাবেই জমা করে। আর r+1 যেন array-র বাইরে না যায়, সেজন্য diff দৈর্ঘ্য T+1।

7. Brute force thinking

প্রতিটা interval ধরে তার পুরো range-এ প্রতিটা সময়ে +1:

def imos_brute(intervals, T):
    counts = [0] * T
    for l, r in intervals:
        for t in range(l, r + 1):     # interval-এর প্রতিটা সময়ে +1
            counts[t] += 1
    return counts

সরল, ঠিক উত্তর — প্রতিটা interval তার প্রতিটা সময়-বিন্দুতে একজন যোগ করে।

8. Why brute force may be slow

একটা interval-এ ভেতরের loop চলে (r - l + 1) বার — খারাপ ক্ষেত্রে পুরো timeline, O(T)। m টা interval হলে মোট O(m × T)।

m = 100000, T = 100000 হলে:
  brute force: ~10^10 operation  (O(m·T)) — TLE
  imos way   : m × O(1) (দুটো event) + O(T) prefix ≈ 3×10^5 — দ্রুত

069-এর মতোই অপচয়: একই সময়-বিন্দু বহু interval-এ বারবার +1 পাচ্ছে। অথচ দরকার শুধু "কোথায় ঢোকা, কোথায় বেরোনো" — মাঝের প্রতিটা বিন্দু আলাদা ছোঁয়ার দরকার নেই।

9. Better thinking

মূল insight: interval = দুটো event (ঢোকা +1, বেরোনো −1)। সব event difference array-তে O(1) করে বসাও, একবার prefix চালিয়ে প্রতি সময়ের count:

def imos_counts(intervals, T):
    diff = [0] * (T + 1)            # r+1 এর জায়গা
    for l, r in intervals:
        diff[l] += 1               # ঢোকা
        diff[r + 1] -= 1           # বেরোনো (r+1-এ)
    counts = [0] * T
    run = 0
    for t in range(T):
        run += diff[t]             # prefix = এখন কতজন
        counts[t] = run
    return counts

m টা O(1) event + একটা O(T) prefix pass = O(m + T)। brute-এর m×T থেকে বিশাল লাফ।

10. Thinking tweak

আসল "আহা!" মুহূর্ত: একটা ব্যবধান (interval) আসলে দুটো প্রান্তিক ঘটনা — শুরুতে +1, শেষের পরে −1। পুরো উপস্থিতি-সময়কে দুটো event-এ নামিয়ে আনা, তারপর running total দিয়ে প্রতি মুহূর্তের অবস্থা ফেরানো।

এটা 069-এরই দৃষ্টিভঙ্গি-বদল: range update (069) আর "কতজন উপস্থিত" (imos) — একই difference+prefix, ভিন্ন গল্প। আর এই "ব্যবধান → event" অনুবাদটাই পরের ধাপ sweep line (080)-এর বীজ: timeline যখন বিশাল বা বিক্ষিপ্ত, তখন array-র বদলে শুধু event গুলো sort করে হাঁটব।

11. Step-by-step dry run

interval [(0,2), (1,3), (4,4)], T=5। diff = [0,0,0,0,0,0] (দৈর্ঘ্য 6):

Event বসানো:

interval	diff পরিবর্তন	diff এখন
(0,2)	diff[0]+=1, diff[3]-=1	[1, 0, 0, -1, 0, 0]
(1,3)	diff[1]+=1, diff[4]-=1	[1, 1, 0, -1, -1, 0]
(4,4)	diff[4]+=1, diff[5]-=1	[1, 1, 0, -1, 0, -1]

prefix (running count):

t	diff[t]	run	counts[t]
0	1	1	1
1	1	2	2
2	0	2	2
3	-1	1	1
4	0	1	1

শেষ অবস্থা: counts = [1, 2, 2, 1, 1]। সর্বোচ্চ overlap = 2 (time 1, 2)। brute force-ও একই দেয় ✓।

12. Python solution

def imos_counts(intervals, T):
    """প্রতিটা সময়-বিন্দু (0..T-1)-এ কতজন উপস্থিত; imos = difference + prefix, O(m + T)।
    interval [l, r] inclusive: ঢোকা diff[l] += 1, বেরোনো diff[r+1] -= 1।"""
    diff = [0] * (T + 1)
    for l, r in intervals:
        diff[l] += 1
        diff[r + 1] -= 1
    counts = [0] * T
    run = 0
    for t in range(T):
        run += diff[t]
        counts[t] = run
    return counts


def imos_brute(intervals, T):
    """ধীর O(m·T) version — interval ধরে প্রতি বিন্দুতে +1; মিলিয়ে দেখার জন্য।"""
    counts = [0] * T
    for l, r in intervals:
        for t in range(l, r + 1):
            counts[t] += 1
    return counts


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert imos_counts([(0, 2), (1, 3), (4, 4)], 5) == [1, 2, 2, 1, 1]
assert imos_counts([(0, 4)], 5) == [1, 1, 1, 1, 1]
assert imos_counts([(1, 1), (1, 1)], 3) == [0, 2, 0]   # একই বিন্দুতে দুজন
assert imos_counts([(0, 0), (2, 2)], 3) == [1, 0, 1]   # মাঝে কেউ নেই
assert imos_counts([], 3) == [0, 0, 0]                 # কোনো interval নেই

# সর্বোচ্চ overlap = max(counts):
assert max(imos_counts([(0, 2), (1, 3), (4, 4)], 5)) == 2

# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(37)
for _ in range(500):
    T = random.randint(1, 12)
    m = random.randint(0, 6)
    intervals = []
    for _ in range(m):
        l = random.randint(0, T - 1)
        r = random.randint(l, T - 1)
        intervals.append((l, r))
    assert imos_counts(intervals, T) == imos_brute(intervals, T)

print(imos_counts([(0, 2), (1, 3), (4, 4)], 5))   # [1, 2, 2, 1, 1]
print(max(imos_counts([(0, 2), (1, 3), (4, 4)], 5)))  # 2
print("সব test pass!")

13. Line-by-line explanation

diff = [0] * (T + 1)

difference array, T+1 ঘর — বাড়তি ঘরটা diff[r+1]-এর জন্য, যখন r = T-1।

for l, r in intervals:
    diff[l] += 1
    diff[r + 1] -= 1

প্রতিটা interval দুটো event-এ: l-এ ঢোকা (+1), r+1-এ বেরোনো (−1)। range যত বড়ই হোক, দুটো দাগ — তাই O(1)। (069-এর x-এর জায়গায় এখানে +1।)

run = 0
for t in range(T):
    run += diff[t]
    counts[t] = run

prefix sum — running count রাখছি, যা প্রতিটা সময়ে "এ পর্যন্ত মোট ঢোকা − বেরোনো" = এখন কতজন ভেতরে। +1 event count বাড়ায়, −1 কমায়।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + random interval-এ fast আর brute মিলিয়ে দেখছে (brute-force cross-check), max-overlap সহ। সব মিললে সব test pass!।

14. Output walkthrough

intervals = [(0,2), (1,3), (4,4)], T=5:

• event বসানো: diff = [1, 1, 0, -1, 0, -1]
• prefix: run যায় 1, 2, 2, 1, 1 → counts = [1, 2, 2, 1, 1] → প্রথম print
• max(counts) = 2 → দ্বিতীয় print
• সব assert pass → সব test pass!

ছাপা output:

[1, 2, 2, 1, 1]
2
সব test pass!

15. Time complexity

O(m + T) — m টা interval প্রতিটা O(1) (দুটো event), তারপর একটা O(T) prefix pass। brute-এর O(m × T)-এর তুলনায় বিশাল উন্নতি, বিশেষত লম্বা interval-এ।

16. Space complexity

O(T) — difference array (T+1) আর counts array (T)। interval সংখ্যার উপর আলাদা জায়গা লাগে না (event সরাসরি diff-এ জমে)।

17. Common mistakes

1. diff[r+1] -= 1 এর জায়গায় diff[r] -= 1 — তাহলে time r-এর অতিথিও গোনা বন্ধ হয়ে যায়, যদিও সে r-এ উপস্থিত। inclusive interval-এ বেরোনো r+1-এ।
2. diff দৈর্ঘ্য T (T+1 না) — r = T-1 হলে diff[r+1] = diff[T] out-of-range; T+1 রাখো।
3. inclusive vs exclusive interval গুলিয়ে ফেলা — [l, r] inclusive হলে r+1-এ −1; [l, r) exclusive হলে r-এ −1। প্রশ্নের convention মিলাও।
4. event আর count-এর ক্রম — সব interval-এর event আগে বসাও, তারপর prefix; মাঝপথে count পড়লে ভুল।
5. max overlap-এ prefix না চালানো — শুধু diff-এ max নিলে ভুল; "একসাথে কতজন" পেতে prefix (running count)-এর উপর max।

18. Harder problems that inherit this idea

• LeetCode — Car Pooling (https://leetcode.com/problems/car-pooling/) — interval-এ যাত্রী +/−, capacity চেক; হুবহু imos।
• LeetCode — My Calendar II / Meeting Rooms II (https://leetcode.com/problems/meeting-rooms-ii/) — সর্বোচ্চ overlap = কয়টা room লাগবে; imos/sweep।
• 080 (Sweep Line Intro) — এই repo-তে পরের ধাপ: timeline বিশাল হলে array নয়, event sort করে sweep।

19. Pattern learned

Imos method (interval → +1/−1 events → prefix) — diff[l] += 1; diff[r+1] -= 1, শেষে prefix = প্রতি বিন্দুতে count। বড় শিক্ষা: একটা ব্যবধানকে দুটো প্রান্তিক ঘটনায় নামাও (ঢোকা +1, বেরোনো −1); running total প্রতি মুহূর্তের অবস্থা ফেরায় — এটাই difference array-র event-রূপ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "imos = interval-কে diff[l] += 1; diff[r+1] -= 1 event-এ ভেঙে শেষে prefix; count = এখন কতজন। difference array-রই event-চোখ। সর্বোচ্চ overlap = max(prefix)। O(m + T)।"

পরের ধাপ → 080 — Sweep Line Intro (timeline বিশাল হলে array নয়, event sort করে sweep)।

ফিরে দেখা: শিকড় → 069 — Difference Array · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

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