080 — Sweep Line Intro

এটাই এই level-এর শেষ note — অভিনন্দন, তুমি প্রায় Level 5 শেষ করে ফেললে! 079-এর imos-এ timeline একটা ছোট array ছিল, তাই প্রতিটা সময়-বিন্দুতে দাগ দেওয়া যেত। কিন্তু timeline যখন বিশাল (10^9) বা ভগ্নাংশ — তখন array বানানো অসম্ভব। সমাধান সুন্দর: পুরো timeline নয়, শুধু event গুলো (ঢোকা/বেরোনো) sort করে বাঁ থেকে ডানে "ঝাড়ু" চালাও। এটাই sweep line — interval-জগতের master key। ধীরে পড়ো; tie-এর নিয়মটাই আসল সূক্ষ্মতা।

Source

• Original source: Classic technique (sweep line — sorted events)
• Platform: Classic technique — https://usaco.guide/silver/sorting-custom (এবং LeetCode Meeting Rooms II — https://leetcode.com/problems/meeting-rooms-ii/)
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Medium
• Pattern: sweep line (sort +1/−1 events, running count)
• Basic idea inherited from: 079 — Imos Method Basic

1. Problem in simple words

কিছু interval দেওয়া — প্রতিটা [l, r) মানে একটা কাজ/মিটিং যা সময় l-এ শুরু হয়ে r-এ শেষ (half-open: r বিন্দুতে আর চলছে না)। তোমাকে বলতে হবে — কোনো এক মুহূর্তে সর্বোচ্চ কতগুলো interval একসাথে চলছে? (এটাই, যেমন, কয়টা meeting room লাগবে।)

যেমন [(1,4), (2,5), (3,6)] হলে উত্তর 3 — সময় 3-এর কাছাকাছি তিনটাই একসাথে চলছে। coordinate বড় হতে পারে, তাই 079-এর মতো প্রতিটা সময়-বিন্দুর array বানানো যাবে না; শুধু event ধরে কাজ করতে হবে।

2. What is the math idea?

মূল idea হলো sweep line — সব শুরু/শেষ-কে event বানিয়ে sort করে, একটা কল্পিত উল্লম্ব রেখা বাঁ থেকে ডানে "ঝাড়ু" দেওয়া।

প্রতিটা interval [l, r) থেকে দুটো event: (l, +1) (শুরু) আর (r, −1) (শেষ)। সব event coordinate অনুযায়ী sort করো। তারপর বাঁ থেকে ডানে যেতে যেতে একটা cur (এখন কয়টা চলছে) রাখো — +1-এ বাড়াও, −1-এ কমাও। পথে সর্বোচ্চ cur-ই উত্তর:

events = [(l, +1) for each] + [(r, -1) for each]
sort events;  cur += delta;  best = max(best, cur)

এটা imos-এরই (079) sorted-event রূপ — array-র জায়গায় sorted list, প্রতিটা সময়-বিন্দু নয় শুধু "যেখানে কিছু বদলায়" সেই বিন্দুগুলো।

3. Which basic idea does this inherit from?

সরাসরি 079 (Imos Method Basic) থেকে। 079-এ event বসত একটা array-র index-এ (diff[l] += 1), তারপর prefix। এখানে timeline বিশাল/বিক্ষিপ্ত বলে array নেই — event গুলো sort করে সেই prefix-চিন্তাই sorted order-এ চালাই।

মূল পার্থক্য: imos-এর diff array index-ভিত্তিক (O(T) জায়গা), sweep-এর event list coordinate-ভিত্তিক (O(m) জায়গা, T-নিরপেক্ষ)। তাই বিশাল coordinate-এ sweep চলে, imos চলে না। প্রায় coordinate compression-এর ধারণা — শুধু যেখানে বদল, সেই বিন্দু। 079-এর event-চিন্তা না থাকলে এই sort-ভিত্তিক রূপ বোঝা কঠিন।

4. Real-life analogy

ভাবো একটা ব্যস্ত হাসপাতালের OPD, আর তুমি জানতে চাও সর্বোচ্চ কতজন রোগী একসাথে ভেতরে ছিল — যাতে কতটা চেয়ার লাগবে বোঝা যায়। কিন্তু দিনটা লম্বা, প্রতি সেকেন্ড গোনা বোকামি।

বরং শুধু দরজার ঘটনা লেখো: কে কখন ঢুকল, কে কখন বেরোল। তারপর সব ঘটনা সময় অনুযায়ী সাজিয়ে, একটা কল্পিত ঘড়ি বাঁ থেকে ডানে চালাও — ঢোকা দেখলে গণনা +1, বেরোনো দেখলে −1। চলার পথে যে সর্বোচ্চ সংখ্যায় পৌঁছালে, ততগুলো চেয়ার লাগবে।

পুরো দিন নয়, শুধু ঘটনার মুহূর্তগুলোতে থামলেই চলে — কারণ দুই ঘটনার মাঝে সংখ্যা বদলায় না। এই "শুধু পরিবর্তন-বিন্দুতে থামা ঝাড়ু" হলো sweep line।

5. Visual explanation

[(1,4), (2,5), (3,6)] (half-open [l, r))। event বানিয়ে sort:

interval [1,4): (1, +1), (4, -1)
interval [2,5): (2, +1), (5, -1)
interval [3,6): (3, +1), (6, -1)

sort করে (coordinate বাড়ন্ত; tie হলে -1 আগে, +1 পরে):
  (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)

বাঁ থেকে ডানে ঝাড়ু (cur = এখন কয়টা চলছে):
  event:   (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)
  cur:        1      2      3      2      1      0
  best:       1      2      3      3      3      3

সর্বোচ্চ overlap = 3   (সময় 3-এর পর তিনটাই একসাথে)

আর touching interval-এর ছবি ([1,2), [2,3) — শুধু ছুঁয়ে আছে, overlap নয়):

events sort: (1,+1) (2,-1) (2,+1) (3,-1)
                          ↑ tie at 2: -1 আগে!
cur:            1      0      1      0
best = 1     (ঠিক — ওরা overlap করে না, শুধু ছোঁয়)

মূল কথা: একই coordinate-এ শেষ (−1) আর শুরু (+1) থাকলে, half-open interval-এ শেষ আগে process করো — নইলে শুধু-ছোঁয়া interval-কে ভুল করে overlap গুনবে।

6. Example input and output

intervals (half-open [l, r))    -> max overlap
-----------------------------------------------------
[(1,4), (2,5), (3,6)]           -> 3
[(1,2), (2,3), (3,4)]           -> 1     (শুধু ছোঁয়, overlap নয়)
[(0,10)]                        -> 1
[(1,3), (1,3), (1,3)]           -> 3     (তিনটাই একই, পুরো overlap)
[(0,1), (1,2), (0,2)]           -> 2
[]                              -> 0     (কোনো interval নেই)

সবচেয়ে গুরুত্বপূর্ণ edge case: tie at same coordinate. half-open [l, r)-এ একই বিন্দুতে শেষ আর শুরু মিললে শেষ আগে (−1 before +1) — তাই [(1,2),(2,3)] overlap নয়, উত্তর 1। closed interval [l, r] চাইলে উল্টো (শুরু আগে) — convention অনুযায়ী tie-নিয়ম বদলায়।

7. Brute force thinking

প্রতিটা সম্ভাব্য বিন্দু (interval-এর শুরুগুলো যথেষ্ট) ধরে গুনি কতগুলো interval সেটা ঢাকে:

def max_overlap_brute(intervals):
    if not intervals:
        return 0
    best = 0
    for l, r in intervals:            # candidate বিন্দু = প্রতিটা শুরু
        count = sum(1 for a, b in intervals if a <= l < b)   # half-open
        best = max(best, count)
    return best

সরল, ঠিক উত্তর — প্রতিটা শুরু-বিন্দুতে কতগুলো interval চলছে গোনে (max overlap সবসময় কোনো শুরু-বিন্দুতে ঘটে)।

8. Why brute force may be slow

প্রতিটা candidate বিন্দুর (m টা) জন্য সব interval (m টা) চেক — O(m²)।

m = 100000 হলে:
  brute force: ~10^10 operation  (O(m²)) — TLE
  sweep way  : ~m log m          ≈ 1.7×10^6 — দ্রুত

অপচয়টা: প্রতিটা বিন্দুতে সব interval আবার গোনা। অথচ event sort করে একবার হাঁটলেই running count পাওয়া যায় — প্রতিটা interval মাত্র দুবার (শুরু, শেষ) ছোঁয়া হয়।

9. Better thinking

মূল insight: সব শুরু/শেষ-কে event বানাও, sort করো, একবার হেঁটে running count-এর max নাও:

def max_overlap(intervals):
    events = []
    for l, r in intervals:
        events.append((l, 1))         # শুরু
        events.append((r, -1))        # শেষ
    events.sort(key=lambda e: (e[0], e[1]))   # tie: -1 (শেষ) আগে +1 (শুরু)
    best = cur = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

event বানানো O(m), sort O(m log m), হাঁটা O(m) — মোট O(m log m)। O(m²) থেকে নেমে এল।

10. Thinking tweak

দুটো "আহা!" মুহূর্ত।

প্রথম: পুরো timeline নয়, শুধু পরিবর্তন-বিন্দু (event) দেখো। দুই event-এর মাঝে overlap সংখ্যা বদলায় না, তাই array না বানিয়ে শুধু event sort করে হাঁটলেই চলে — এটাই imos (079)-কে বিশাল/বিক্ষিপ্ত coordinate-এ টেনে নেয়।

দ্বিতীয় (সবচেয়ে সূক্ষ্ম): tie-এর নিয়ম convention-নির্ভর। half-open [l, r)-এ একই বিন্দুতে শেষ(−1) আগে, শুরু(+1) পরে — তাই শুধু-ছোঁয়া interval overlap গোনে না। closed [l, r]-এ উল্টো। sort-key-তে (coord, delta) দিয়ে এটা সামলাই (−1 < +1, তাই −1 আগে)। এই একটা সিদ্ধান্তই tie-bug-এর রক্ষাকবচ — interval problem-এ এখানেই সবচেয়ে বেশি ভুল হয়।

11. Step-by-step dry run

[(1,4), (2,5), (3,6)] (half-open)। event বানিয়ে sort:

events (sort করা): (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)

ঝাড়ু:

event	delta	cur += delta	best
(1, +1)	+1	1	1
(2, +1)	+1	2	2
(3, +1)	+1	3	3
(4, -1)	-1	2	3
(5, -1)	-1	1	3
(6, -1)	-1	0	3

শেষ অবস্থা: best = 3। সময় 3-এর পর তিনটাই একসাথে চলছিল; তারপর একে একে শেষ হলো। brute force-ও 3 দেয় ✓।

12. Python solution

def max_overlap(intervals):
    """সর্বোচ্চ কতগুলো half-open interval [l, r) একসাথে; sweep line, O(m log m)।
    tie at same coordinate: শেষ(-1) আগে, শুরু(+1) পরে — touching overlap নয়।"""
    events = []
    for l, r in intervals:
        events.append((l, 1))
        events.append((r, -1))
    events.sort(key=lambda e: (e[0], e[1]))   # -1 < +1, তাই শেষ আগে
    best = cur = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best


def max_overlap_brute(intervals):
    """ধীর O(m^2) version — প্রতিটা শুরু-বিন্দুতে গোনা; মিলিয়ে দেখার জন্য।"""
    if not intervals:
        return 0
    best = 0
    for l, r in intervals:
        count = sum(1 for a, b in intervals if a <= l < b)
        best = max(best, count)
    return best


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert max_overlap([(1, 4), (2, 5), (3, 6)]) == 3
assert max_overlap([(1, 2), (2, 3), (3, 4)]) == 1   # শুধু ছোঁয়, overlap নয়
assert max_overlap([(0, 10)]) == 1
assert max_overlap([(1, 3), (1, 3), (1, 3)]) == 3   # পুরো overlap
assert max_overlap([(0, 1), (1, 2), (0, 2)]) == 2
assert max_overlap([]) == 0                         # কোনো interval নেই

# fast আর brute একই উত্তর কিনা (random brute-force cross-check):
import random
random.seed(41)
for _ in range(500):
    intervals = []
    for _ in range(random.randint(0, 8)):
        l = random.randint(0, 10)
        r = random.randint(l + 1, 11)   # half-open, r > l নিশ্চিত
        intervals.append((l, r))
    assert max_overlap(intervals) == max_overlap_brute(intervals)

print(max_overlap([(1, 4), (2, 5), (3, 6)]))    # 3
print(max_overlap([(1, 2), (2, 3), (3, 4)]))    # 1
print("সব test pass!")

13. Line-by-line explanation

for l, r in intervals:
    events.append((l, 1))
    events.append((r, -1))

প্রতিটা interval দুটো event-এ ভাঙছি: শুরু (l, +1), শেষ (r, −1)। পুরো interval নয়, শুধু দুই প্রান্তিক ঘটনা।

events.sort(key=lambda e: (e[0], e[1]))

coordinate অনুযায়ী sort; tie হলে দ্বিতীয় key delta — -1 < +1, তাই একই বিন্দুতে শেষ আগে process হয় (half-open convention)। এই sort-key-ই tie-bug সামলায়।

best = cur = 0
for _, delta in events:
    cur += delta
    best = max(best, cur)

বাঁ থেকে ডানে ঝাড়ু — cur এখন কয়টা চলছে (+1-এ বাড়ে, −1-এ কমে), পথে সর্বোচ্চ best-এ রাখি। এটাই running count-এর max, imos-এর prefix-max-এর sorted রূপ।

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

14. Output walkthrough

[(1,4), (2,5), (3,6)]:

• events sort: (1,+1) (2,+1) (3,+1) (4,-1) (5,-1) (6,-1)
• ঝাড়ু: cur যায় 1, 2, 3, 2, 1, 0, best = 3 → প্রথম print
• [(1,2),(2,3),(3,4)] → touching, best = 1 → দ্বিতীয় print
• সব assert pass → সব test pass!

ছাপা output:

3
1
সব test pass!

15. Time complexity

O(m log m) — m টা interval থেকে 2m টা event, sort-এর খরচ O(m log m); তারপর একবার হাঁটা O(m)। sort-ই প্রধান খরচ। brute-এর O(m²) থেকে বড় উন্নতি।

16. Space complexity

O(m) — event list-এ 2m টা entry। লক্ষণীয়: এটা coordinate-এর আকার (T)-নিরপেক্ষ — imos-এর O(T)-র বদলে O(m), তাই বিশাল/বিক্ষিপ্ত timeline-এও চলে।

17. Common mistakes

1. tie-এর নিয়ম ভুল করা — half-open [l, r)-এ একই বিন্দুতে শেষ আগে (−1 before +1); নাহলে touching interval ভুল করে overlap গোনে। sort-key (coord, delta) এটা ঠিক করে।
2. closed vs half-open গুলিয়ে ফেলা — closed [l, r]-এ শুরু আগে (tie উল্টো); convention মিলিয়ে নাও, নইলে প্রান্তে off-by-one।
3. imos array দিয়ে বিশাল coordinate সামলানোর চেষ্টা — coordinate 10^9 হলে array বানানো অসম্ভব; event sort করো (বা coordinate compression)।
4. running max নিতে ভুলে যাওয়া — শুধু শেষ cur নয়, পথে সর্বোচ্চ cur চাই; প্রতি step-এ best = max(best, cur)।
5. শেষ point (r) overlap-এ গোনা (half-open-এ) — [l, r)-এ r বিন্দুতে interval চলছে না; brute-এ a <= p < b (<= b নয়)।

18. Harder problems that inherit this idea

• LeetCode — Meeting Rooms II (https://leetcode.com/problems/meeting-rooms-ii/) — সর্বোচ্চ overlap = ন্যূনতম room; হুবহু এই sweep।
• LeetCode — Car Pooling (https://leetcode.com/problems/car-pooling/) — interval-এ যাত্রী, capacity চেক (imos/sweep)।
• LeetCode — Merge Intervals / The Skyline Problem (https://leetcode.com/problems/the-skyline-problem/) — sweep line-এর গভীর প্রয়োগ (event + heap)।

19. Pattern learned

Sweep line (sorted +1/−1 events, running count) — interval → events, sort, হেঁটে running count-এর max। বড় শিক্ষা: timeline বিশাল/বিক্ষিপ্ত হলে array নয় — শুধু পরিবর্তন-বিন্দু (event) sort করে ঝাড়ু চালাও; tie-এর নিয়ম (half-open হলে শেষ আগে) convention-এ স্থির করো। এটাই imos-এর sorted রূপ।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "sweep line = interval-কে (l,+1),(r,-1) event-এ ভেঙে sort করে running count-এর max। বিশাল coordinate-এ imos-এর জায়গায় এটা (O(m log m), T-নিরপেক্ষ)। tie: half-open হলে শেষ(-1) আগে। interval-জগতের master key।"

পরের ধাপ → পুরো Level 5 শেষ! এগিয়ে যাও Level 6: Two Pointers ও Sliding Window-এ।

ফিরে দেখা: শিকড় → 079 — Imos Method Basic · এই 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" লেখো।