Skip to content

017 — My Calendar III

Source

  • Original source: LeetCode 732 — My Calendar III
  • Platform: LeetCode — https://leetcode.com/problems/my-calendar-iii/
  • Topic: segment tree and fenwick tree
  • Difficulty: Hard
  • Pattern: sweep line / lazy-tree teaser (interval-এ +1, max overlap track)
  • Basic idea inherited from: intervals, segment-on-values

1. Problem in simple words

একটা calendar-এ একে একে event বুক করা হচ্ছে। প্রতিটা event একটা half-open interval [start, end) — অর্থাৎ start থেকে শুরু, কিন্তু end ছোঁয় না।

প্রতিবার একটা নতুন event যোগ করার পর বলতে হবে: এই মুহূর্ত পর্যন্ত যত event যোগ হয়েছে, তাদের মধ্যে কোনো একটা সময়-বিন্দুতে সর্বোচ্চ কতগুলো event একসাথে চলছে (maximum overlap / k-booking)।

book [10, 20) -> 1   (এক জায়গাতেই একটা)
book [50, 60) -> 1   (আলাদা সময়, এখনো max 1)
book [10, 40) -> 2   ([10,20) আর [10,40) ওভারল্যাপ করছে)
book [ 5, 15) -> 3   ([10,15)-এ তিনটাই চলছে)
book [ 5, 10) -> 3
book [25, 55) -> 3

2. Which basic idea does this inherit from?

এটা দাঁড়িয়ে আছে intervals আর segment-on-values-এর উপর।

  • Intervals থেকে: একটা interval [s, e)-কে দুটো ঘটনা হিসেবে দেখা — s-এ "একটা event শুরু" (+1), e-তে "একটা event শেষ" (−1)। এটাই classic sweep line / difference-array চিন্তা (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/)।
  • Segment-on-values থেকে: events টাইম-axis-এর উপর +1/−1 করে; কোনো বিন্দুতে চলমান event-সংখ্যা মানে ওই বিন্দু পর্যন্ত prefix sum, আর আমরা চাই সব বিন্দুর সর্বোচ্চ prefix sum — যেটা range-update + range-max segment tree বা সহজ difference-array-তে বেরোয়।

3. What is the hidden math or logic?

লুকানো logic একটা difference array / sweep: interval [s, e)-এ "+1 everywhere" করা মানে শুধু s-এ +1 আর e-তে −1 লেখা। সব ঘটনা সময়-অনুযায়ী sort করে বাঁ-থেকে-ডান prefix sum চালালে, যেকোনো মুহূর্তে চলমান event-সংখ্যা বেরিয়ে আসে; সেই prefix sum-এর সর্বোচ্চ মান-ই উত্তর।

পুরো segment-tree version এই "interval-এ +1, global max"-কেই lazy propagation দিয়ে করে — একটা node-এর পুরো segment cover হলে নিচে না নেমে গায়ে "+1" sticky note লেখা (../segment-tree.md section 9-এর teaser)।

4. Which data structure is needed?

দুটো পথ, একই উত্তর:

  • Teaser path (clean): একটা sorted map (key = time-point, value = net change)। প্রতিটা booking-এ delta[s] += 1, delta[e] -= 1; তারপর সময়-অনুযায়ী prefix sum-এর max।
  • Tree path (এই folder-এর target): একটা range-update + range-max segment tree with lazy propagation, time-values compress করে।

5. Why this data structure fits

এটা plain prefix sums-এ আটকায় না, কারণ event-গুলো dynamically আসছে আর প্রতিবার max লাগছে — frozen array নয়। আবার এটা range update (একটা পুরো interval-এ +1) + max query — যেখানে Fenwick স্বাভাবিকভাবে চলে না (../fenwick-tree.md section 8: range update + max = segment tree)।

Lazy-propagation segment tree ঠিক এই "interval-এ যোগ করো, সর্বোচ্চ track করো" জোড়ার জন্য বানানো — তাই এই problem এই topic-এর lazy-propagation teaser হিসেবে নিখুঁত।

6. Real-life analogy

ভাবো একটা meeting room-এর সারাদিনের timeline একটা লম্বা টেপের মতো টানানো। প্রতিটা নতুন meeting এলে তুমি তার শুরু-বিন্দুতে একটা "+1" sticker আর শেষ-বিন্দুতে একটা "−1" sticker সাঁটো।

দিনের কোন মুহূর্তে সবচেয়ে ভিড় জানতে তুমি বাঁ থেকে ডান টেপ বরাবর হাঁটো, sticker-গুলো যোগ করতে করতে একটা চলমান গোনা রাখো — সেই গোনা যেখানে সর্বোচ্চ, সেটাই দিনের সবচেয়ে ব্যস্ত মুহূর্ত। প্রতিটা ঘরের প্রতি মিনিট আলাদা করে গুনতে হয় না।

7. Visual explanation

বুক করা intervals আর তাদের +1/−1 sweep:

events:  [10,20)  [50,60)  [10,40)  [5,15)

time-axis-এ delta sticker:
   5: +1        10: +1, +1     15: -1      20: -1
  40: -1        50: +1         60: -1

সময়-অনুযায়ী সাজিয়ে running sum (prefix):
  t=5  : +1            -> running 1
  t=10 : +1 +1         -> running 3   <- max এখানে
  t=15 : -1            -> running 2
  t=20 : -1            -> running 1
  t=40 : -1            -> running 0
  t=50 : +1            -> running 1
  t=60 : -1            -> running 0

সর্বোচ্চ running = 3

8. Example input and output

book [10, 20) -> 1
book [50, 60) -> 1
book [10, 40) -> 2
book [ 5, 15) -> 3
book [ 5, 10) -> 3
book [25, 55) -> 3

half-open মনে রেখো: [5,10) আর [10,20) overlap করে না (10 ছোঁয় না)।

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা booking-এর পর, এ পর্যন্ত আসা সব interval-কে দুটো (time, delta) ঘটনায় ভাঙো, সব ঘটনা sort করো, prefix sum চালিয়ে max বের করো।

on each book(s, e):
    events += [(s, +1), (e, -1)]
    sort events by time (e আগে -1, একই time-এ)
    running = 0; best = 0
    for (_, d) in events: running += d; best = max(best, running)
    return best

10. Why brute force is slow

প্রতিটা booking-এ এ পর্যন্ত আসা সব event আবার sort করা হয় — k-তম booking-এ O(k log k)। n-টা booking মিলিয়ে O(n² log n)। n বড় হলে ধীর। উত্তর: difference-array-টা একবার maintain করো (re-sort না করে), অথবা lazy segment tree-তে প্রতি booking O(log n)।

11. Key observation

মূল observation: একটা পুরো interval-এ "+1" করা = শুধু দুই প্রান্তে +1/−1 লেখা। আর কোনো বিন্দুর চলমান overlap = ওই বিন্দু পর্যন্ত delta-গুলোর prefix sum। তাই max overlap = এই sweep-এর সর্বোচ্চ prefix sum — পুরো timeline না ঘেঁটে শুধু boundary-গুলো গুনলেই চলে।

12. Optimized intuition

একটা sorted map-এ delta জমাও: প্রতিটা book(s, e)-এ delta[s] += 1, delta[e] -= 1। তারপর key-গুলো সময়-অনুযায়ী হেঁটে running sum-এর max-ই উত্তর।

Tree version: time-values compress করে একটা lazy segment tree-তে [s, e)-এ range +1 করো (পুরো-cover node-এ sticky note), আর root-এর global max return করো — প্রতি booking O(log n)।

13. Thinking tweak

মোচড়: "প্রতিটা মুহূর্তে কতগুলো event চলছে আলাদা করে গুনব" ভাবার বদলে ভাবো "প্রতিটা interval শুধু দুটো boundary-ঘটনা; চলমান গোনা মানে boundary-গুলোর prefix sum।" একটা continuous overlap-হিসাব কয়েকটা +1/−1 marker-এ গুটিয়ে যায়।

14. Step-by-step dry run

booking ক্রম [10,20), [50,60), [10,40):

  1. [10,20): delta {10:+1, 20:-1}। sweep: t10→1, t20→0। max = 1।
  2. [50,60): delta {10:+1, 20:-1, 50:+1, 60:-1}। sweep: t10→1, t20→0, t50→1, t60→0। max = 1।
  3. [10,40): delta {10:+2, 20:-1, 40:-1, 50:+1, 60:-1}। sweep: t10→2, t20→1, t40→0, t50→1, t60→0। max = 2।

প্রতি step-এর শেষে return: 1, 1, 2। ✓

15. Python solution

class MyCalendarThree:
    """Sweep line: প্রতিটা interval [s, e)-কে delta[s] += 1, delta[e] -= 1 করে
    জমাই; কোনো মুহূর্তের overlap = ওই বিন্দু পর্যন্ত prefix sum; উত্তর = max prefix।
    এটাই 'interval-এ +1, global max' — যেটা lazy-propagation segment tree-রও কাজ
    (`../segment-tree.md` section 9-এর teaser)। এখানে clean sorted-map রূপ।"""

    def __init__(self):
        self.delta = {}                    # time-point -> net change

    def book(self, start, end):
        self.delta[start] = self.delta.get(start, 0) + 1   # interval শুরু
        self.delta[end] = self.delta.get(end, 0) - 1       # interval শেষ
        running = 0
        best = 0
        for t in sorted(self.delta):       # সময়-অনুযায়ী sweep
            running += self.delta[t]
            best = max(best, running)
        return best


def brute(intervals):
    # obviously-correct reference: প্রতিটা booking-এর পরের max overlap
    # ছোট integer coordinate-এ unit cell গুনে (half-open [s, e))
    out = []
    seen = []
    for s, e in intervals:
        seen.append((s, e))
        lo = min(a for a, _ in seen)
        hi = max(b for _, b in seen)
        best = 0
        for t in range(lo, hi):            # প্রতিটা unit time-slot [t, t+1)
            cnt = sum(1 for a, b in seen if a <= t < b)
            best = max(best, cnt)
        out.append(best)
    return out


# ---- tests ----
cal = MyCalendarThree()
assert cal.book(10, 20) == 1
assert cal.book(50, 60) == 1
assert cal.book(10, 40) == 2
assert cal.book(5, 15) == 3
assert cal.book(5, 10) == 3
assert cal.book(25, 55) == 3

# half-open: পাশাপাশি interval overlap করে না
cal2 = MyCalendarThree()
assert cal2.book(0, 10) == 1
assert cal2.book(10, 20) == 1              # 10 ছোঁয় না, তাই max এখনো 1
assert cal2.book(5, 15) == 2              # [5,15) দুটোর সাথেই 2-overlap তৈরি করে

# হুবহু একই slot বারবার -> overlap বাড়তেই থাকে
cal3 = MyCalendarThree()
assert cal3.book(1, 2) == 1
assert cal3.book(1, 2) == 2              # একই slot, দুটো একসাথে

# random fuzz: sweep-map vs unit-cell brute (ছোট coordinate)
import random
random.seed(17)
for _ in range(400):
    cal_f = MyCalendarThree()
    ivs = []
    for _ in range(random.randint(1, 8)):
        a = random.randint(0, 10)
        b = random.randint(a + 1, 11)     # half-open, e > s
        ivs.append((a, b))
    expected = brute(ivs)
    got = [cal_f.book(s, e) for s, e in ivs]
    assert got == expected, (ivs, got, expected)

print("সব test pass!")

16. Line-by-line code explanation

  • self.delta — time-point → net change map; sweep-line-এর difference array।
  • book(start, end) — start-এ +1 (event শুরু), end-এ −1 (event শেষ); half-open তাই end ছোঁয় না।
  • for t in sorted(self.delta) — সময়-অনুযায়ী prefix sum চালাই; best ধরে রাখে সর্বোচ্চ চলমান overlap।
  • brute — ছোট integer coordinate-এ প্রতিটা unit slot [t, t+1) গুনে max বের করা reference।
  • random fuzz — sweep-map-এর উত্তর unit-cell brute-এর সাথে 400 case-এ মেলায়।

17. Output walkthrough

প্রতিটা book-এর পর sweep পুরো delta map হেঁটে max overlap দেয়: [10,20)→1, [50,60)→1 (আলাদা সময়), [10,40)→2 (10..20 overlap), [5,15)→3 (10..15-এ তিনটা)। পরের দুটো আর 3 ছাড়ায় না। half-open আর "হুবহু একই slot দুবার" case-ও সঠিক, আর 400 random fuzz unit-cell brute-এর সাথে মেলে। শেষে print: সব test pass!।

18. Time complexity

এই sweep-map version: প্রতিটা book-এ পুরো map sort করে হাঁটা — k-তম call-এ O(k log k), n call-এ O(n² log n)। Lazy-propagation segment tree (compressed times) version প্রতি booking O(log n), মোট O(n log n) — এটাই scalable target।

19. Space complexity

O(n) — delta map-এ সর্বোচ্চ 2n-টা distinct time-point (প্রতিটা booking দুটো boundary যোগ করে)।

20. Common mistakes

  • half-open [s, e)-কে closed [s, e] ভাবা — তাহলে পাশাপাশি interval ভুল করে overlap গোনা হয়; end-এ −1 ঠিক end-এই, পরে নয়।
  • একই time-point-এ আগের delta overwrite করা (= 1 লেখা) +=-এর বদলে — একাধিক event একই বিন্দুতে শুরু হলে গোনা হারায়।
  • Tree path-এ time compress না করে raw 10^9 coordinate-এ tree বানাতে চাওয়া — memory blow-up; আগে compress করো।

21. Which basic problem this inherits from

ভিত্তি: difference-array / sweep line (../../01-math-based-programming-fundamentals/05-prefix-difference-contribution/-এর interval-এ +1 trick) + segment-on-values with lazy propagation (../segment-tree.md section 9 teaser)। base tree code ../implementation.py-তে।

22. Similar harder problems

23. Pattern learned

Sweep line / lazy-tree teaser: interval-কে boundary-ঘটনায় (+1/−1) ভেঙে prefix sum-এর max বের করা। এই "interval-এ যোগ করো, global max track করো" জোড়াই lazy-propagation segment tree-র canonical use — boundary marker দিয়ে continuous overlap-হিসাব গুটিয়ে ফেলা।

24. Final summary

ভবিষ্যতের আমাকে: "interval-এ +1, সর্বোচ্চ overlap" দেখলেই sweep line মনে করবে — শুরুতে +1, শেষে −1, তারপর সময়-অনুযায়ী prefix sum-এর max। half-open boundary-তে সাবধান। বড় input-এ এই sweep-টাই lazy-propagation segment tree-তে রূপ নেয় (range update + range max), প্রতি booking O(log n) — এই topic-এর lazy teaser-এর আসল মুখ।

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