Skip to content

011 — Merge Intervals

Source

  • Original source: Classic capstone interview problem (sort then sweep)
  • Platform: LeetCode — https://leetcode.com/problems/merge-intervals/
  • Topic: sorting + arrays
  • Difficulty: Medium
  • Pattern: Sort by start, তারপর এক-পাসে overlap collapse (sweep)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 03 sorting (interval-গুলোকে start দিয়ে sort করে একটা সাজানো timeline বানানো) আর 02 arrays (সেই সাজানো list-এর উপর বাঁ-থেকে-ডান একবার scan করে পাশাপাশি জিনিস compare করা)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে কতগুলো interval দেওয়া আছে, প্রতিটা [start, end] রূপে — যেমন কোনো মিটিংয়ের শুরু আর শেষ সময়। এদের মধ্যে কিছু একে অন্যের সাথে ছুঁয়ে যায় বা overlap করে। তোমার কাজ: যেসব interval overlap করে, তাদের একসাথে জুড়ে একটা বড় interval বানাও, আর শেষে এমন একগুচ্ছ আলাদা (non-overlapping) interval ফেরত দাও যেগুলো একই জায়গা cover করে।

intervals : [[1, 3], [2, 6], [8, 10], [15, 18]]
[1,3] আর [2,6] overlap করে -> জুড়ে [1,6]
ফলাফল    : [[1, 6], [8, 10], [15, 18]]

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 03 sorting থেকে: interval-গুলোকে আগে start time দিয়ে sort করা। এক বার সাজানো হয়ে গেলে, যে interval-গুলো overlap করতে পারে তারা list-এ পাশাপাশি বসে — তখন আর সব pair মিলিয়ে দেখার দরকার নেই।
  • 02 arrays থেকে: সেই সাজানো array-র উপর single pass scan, যেখানে প্রতি step-এ শুধু "আগের জমানো interval" আর "এখনকার interval"-কে compare করি।

একা sorting দেয় "overlap-রা পাশাপাশি" এই গ্যারান্টি; একা array-scan দেয় পাশাপাশি জিনিস জোড়ার ক্ষমতা। দুটো মিললে O(n log n)।

3. What is the hidden math or logic?

লুকানো logic একটা overlap invariant: যদি list start দিয়ে sorted হয়, তাহলে নতুন interval [s, e] আগের জমানো interval [ps, pe]-র সাথে overlap করে ঠিক তখনই যখন s <= pe। কারণ sort করায় s >= ps নিশ্চিত, তাই শুধু s যদি pe-র ভেতরে (বা সমান) পড়ে তবেই দুটো ছুঁয়ে আছে। overlap হলে নতুন end হয় max(pe, e) (একটা আরেকটাকে গিলে ফেলতে পারে, তাই max)।

4. Which data structure is needed?

  • ইনপুট হিসেবে interval-দের একটা list/array (02 arrays)।
  • ফলাফল জমাতে আরেকটা result list (merged), যেটায় শেষ element-টাই বারবার "চলমান জমানো interval"-এর কাজ করে।

কোনো ভারী structure লাগে না — sort + একটা output list-ই যথেষ্ট।

5. Why this data structure fits

আমাদের শুধু দরকার "সর্বশেষ জমানো interval"-টাকে দ্রুত দেখা ও বাড়ানো। একটা result list-এর শেষ element (merged[-1]) ঠিক সেই কাজটা O(1)-এ করে — হয় তার end বাড়াই, নয় নতুন interval push করি। sort (03) overlap-দের পাশাপাশি এনে দেওয়ায় আমাদের কখনো পিছনে ফিরে তাকাতে হয় না, তাই এই append-only list-ই (02 arrays-এর সরল রূপ) নিখুঁত। এ কারণেই extra space শুধু output, আর কাজটা single pass।

6. Real-life analogy

ভাবো তুমি সারাদিনের সব মিটিং একটা ক্যালেন্ডারে বসাচ্ছ, শুরুর সময় অনুযায়ী সাজিয়ে। নতুন একটা মিটিং নিলে দেখো — এটা কি আগের চলতি মিটিং শেষ হওয়ার আগেই শুরু হচ্ছে? হলে দুটো আসলে একটাই লম্বা ব্যস্ত-সময়, তাই শেষ সময়টা যেটা বেশি দূর সেটা রাখো। নাহলে আগের মিটিং শেষ, নতুন আলাদা একটা শুরু। দিনের শেষে তোমার হাতে থাকে কয়েকটা পরিষ্কার "ব্যস্ত block"।

7. Visual explanation

[[1,3],[2,6],[8,10],[15,18]] — start দিয়ে sort (এখানে আগেই sorted), তারপর sweep:

sorted : [1,3] [2,6] [8,10] [15,18]

নাও [1,3]   -> merged খালি, push      merged = [[1,3]]
নাও [2,6]   -> 2 <= 3 ? হ্যাঁ overlap   end = max(3,6)=6   merged = [[1,6]]
নাও [8,10]  -> 8 <= 6 ? না             push                merged = [[1,6],[8,10]]
নাও [15,18] -> 15 <= 10 ? না           push                merged = [[1,6],[8,10],[15,18]]

ফলাফল = [[1,6],[8,10],[15,18]]

8. Example input and output

Input : [[1,3],[2,6],[8,10],[15,18]]   -> Output: [[1,6],[8,10],[15,18]]
Input : [[1,4],[4,5]]                  -> Output: [[1,5]]   # ছোঁয়াও overlap (4 <= 4)

Edge case 1 (একটা interval): [[5,7]]          -> [[5,7]]
Edge case 2 (একটা আরেকটাকে গেলে): [[1,10],[2,3]] -> [[1,10]]
Edge case 3 (unsorted input): [[2,6],[1,3]]   -> [[1,6]]  # আগে sort করতেই হবে

9. Brute force thinking

প্রথম সরল চিন্তা: sort না করে বারবার পুরো list-টা ঘুরে দেখি কোনো দুটো interval overlap করছে কি না; পেলে তাদের জুড়ে দিই, আবার শুরু থেকে দেখি। কোনো overlap আর না পাওয়া পর্যন্ত repeat।

repeat:
    found = False
    প্রতিটা pair (i, j):
        if overlap(i, j):
            ওদের জুড়ে একটা বানাও, দুটো মুছে যোগ করো
            found = True; break
    if not found: break

10. Why brute force is slow

প্রতিবার সব pair মেলানো O(n^2), আর প্রতিটা merge-এর পর আবার শুরু থেকে — সব মিলিয়ে O(n^3) পর্যন্ত যেতে পারে। কারণ আমরা কোনো order ব্যবহার করছি না, তাই একই interval বারবার compare হয়। sort (03) একবার করে নিলে overlap-রা পাশাপাশি বসে, আর single pass-ই (02) যথেষ্ট হয়ে যায়।

11. Key observation

মূল observation: start দিয়ে sort করলে, একটা interval কেবল তার ঠিক-আগের জমানো interval-এর সাথেই overlap করতে পারে — দূরের কারো সাথে নয়। কারণ start বাড়ছে, তাই পরের কোনো interval আগের জমানোটার শুরুর আগে ঢুকতে পারে না। এই এক চিন্তাই O(n^2) compare-কে এক-পাসে নামিয়ে আনে।

12. Optimized intuition

interval-গুলো start দিয়ে sort করো। একটা খালি merged list রাখো। এক এক করে interval নাও: যদি merged খালি হয় বা এখনকার start আগের জমানোটার end-এর চেয়ে বড় হয় (gap আছে), নতুন interval হিসেবে push করো। নাহলে overlap — আগের জমানোটার end-কে max(আগের end, এখনকার end) করে বাড়াও। পুরো list শেষ হলে merged-ই উত্তর।

13. Thinking tweak

মোচড়: "সব pair overlap করে কি না দেখব" ভাবার বদলে আগে sort করে নাও — তখন প্রশ্নটা নেমে আসে শুধু "এখনকার start কি আগের end ছাড়িয়ে গেছে?"-তে। বিশাল pairwise তুলনা একটা সাজানো list-এর উপর single sweep-এ গলে যায়।

14. Step-by-step dry run

Input [[1,4],[2,3],[5,7]]:

  1. start দিয়ে sort: [[1,4],[2,3],[5,7]] (আগেই সাজানো); merged = []
  2. নাও [1,4]: merged খালি → push; merged = [[1,4]]
  3. নাও [2,3]: 2 <= 4 → overlap; end = max(4, 3) = 4; merged = [[1,4]]
  4. নাও [5,7]: 5 <= 4? না → push; merged = [[1,4],[5,7]]
  5. শেষ → return [[1,4],[5,7]]

15. Python solution

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda iv: iv[0])      # start দিয়ে sort (03 sorting)
    merged = [intervals[0][:]]                # প্রথমটা দিয়ে শুরু (copy)
    for s, e in intervals[1:]:                # বাকিগুলো একবার scan (02 arrays)
        if s <= merged[-1][1]:                # এখনকার start আগের end-এর ভেতরে?
            merged[-1][1] = max(merged[-1][1], e)   # overlap -> end বাড়াও
        else:
            merged.append([s, e])             # gap -> নতুন interval
    return merged

# ---- tests ----
assert merge_intervals([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
assert merge_intervals([[1,4],[4,5]]) == [[1,5]]            # ছোঁয়াও overlap
assert merge_intervals([[5,7]]) == [[5,7]]                  # একটা interval
assert merge_intervals([[1,10],[2,3]]) == [[1,10]]         # একটা আরেকটাকে গেলে
assert merge_intervals([[2,6],[1,3]]) == [[1,6]]           # unsorted input
assert merge_intervals([]) == []                           # খালি
assert merge_intervals([[1,4],[0,4]]) == [[0,4]]          # একই end, ছোট start
print("সব test pass!")

16. Line-by-line code explanation

  • if not intervals: return [] — খালি ইনপুটে আগেভাগে খালি list ফেরত, পরের intervals[0] যেন crash না করে।
  • intervals.sort(key=lambda iv: iv[0]) — start দিয়ে সাজাও; এতেই overlap-রা পাশাপাশি বসে (03 sorting)।
  • merged = [intervals[0][:]] — প্রথম interval-এর একটা copy দিয়ে শুরু ([:] যাতে মূল ইনপুট না বদলায়)।
  • for s, e in intervals[1:] — দ্বিতীয় থেকে একবার scan (02 arrays-এর single pass)।
  • if s <= merged[-1][1] — এখনকার start আগের জমানোটার end-এর ভেতরে হলে overlap।
  • merged[-1][1] = max(...) — overlap হলে শেষ জমানোটার end-কে দূরতমটা দিয়ে বাড়াই (একটা আরেকটাকে গিলতে পারে)।
  • else: merged.append([s, e]) — gap থাকলে আলাদা নতুন interval।
  • return merged — সব মিলিয়ে non-overlapping interval-দের list।

17. Output walkthrough

[[1,3],[2,6],[8,10],[15,18]]-এ sort করার পর [1,3] দিয়ে শুরু; [2,6]-এ 2 <= 3 তাই end হয় 6 → [1,6]; [8,10]-এ 8 <= 6 মিথ্যা, তাই আলাদা push; [15,18]-ও তাই → [[1,6],[8,10],[15,18]] — assert pass। ছোঁয়া-overlap (4 <= 4), গিলে ফেলা, unsorted, খালি — সব case সঠিক। শেষে print: সব test pass!।

18. Time complexity

O(n log n) — মূল খরচ sort-এ; তার পরের sweep মাত্র O(n)।

19. Space complexity

O(n) — output merged list সবচেয়ে খারাপ ক্ষেত্রে n-টা interval রাখে (যদি কেউ overlap না করে)। in-place sort ধরলে বাড়তি কাজের memory O(1) (sort-এর নিজস্ব খরচ বাদে)।

20. Common mistakes

  • sort করতে ভুলে যাওয়া — তাহলে "শুধু আগের জমানোটার সাথে compare" যুক্তিটাই ভেঙে যায়।
  • overlap শর্তে < ব্যবহার করা (s < pe) — তখন ছোঁয়া interval ([1,4] আর [4,5]) জোড়া পড়ে না; <= লাগে যদি ছোঁয়াকেও overlap ধরো।
  • end বাড়াতে max না নিয়ে সরাসরি e বসানো — [1,10] আর [2,3]-এ end ভুল করে 3 হয়ে যাবে; দূরতমটা রাখতে max জরুরি।
  • মূল ইনপুট list সরাসরি বদলে ফেলা — copy ([:]) রাখলে side-effect এড়ানো যায়।

21. Which basic problem this inherits from

ভিত্তি: comparator দিয়ে sorting (03 sorting, ../../03-searching-and-sorting/) + সাজানো array-র উপর single-pass scan আর পাশাপাশি compare (02 arrays, ../../02-arrays-and-strings/)। এই দুটো cold জানা থাকলে "sort তারপর sweep" নিজে থেকেই আসে।

22. Similar harder problems

23. Pattern learned

Sort + sweep on intervals: interval-কে start দিয়ে sort করে এক-পাসে "এখনকার start কি আগের end ছাড়িয়েছে?" দেখে overlap collapse করা। interval-জাতীয় যেকোনো merge/overlap problem-এর canonical সূচনা।

24. Final summary

ভবিষ্যতের আমাকে: "interval / range / overlap merge" শুনলেই আগে start দিয়ে sort, তারপর single sweep মনে করবে। চাল — merged[-1] ধরে রাখো, s <= end হলে end = max(...), নাহলে push। <= বনাম < (ছোঁয়া গোনা) আর end-এ max — এই দুটোতেই বেশি ভুল হয়। heap লাগে শুধু "একসাথে কতগুলো active" জানতে চাইলে (Meeting Rooms II)।

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