011 — Merge Intervals

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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 — এখানে মেশে sorting (interval-গুলোকে start দিয়ে sort করে একটা সাজানো timeline বানানো) আর 02 arrays (সেই সাজানো list-এর উপর বাঁ-থেকে-ডান একবার scan করে পাশাপাশি জিনিস compare করা)। দুই tool জোড়া লাগলেই এই problem।

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে কতগুলো 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]]

Input ও 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 করতেই হবে

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

• 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)।

ভেতরের যুক্তি

লুকানো 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)।

কী দিয়ে তথ্য রাখব

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

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ

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

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

[[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]]

ছোট input-এ ধাপে ধাপে

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]]

কোড ও ব্যাখ্যা

Python

Python

def merge_intervals(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda iv: iv[0])      # start দিয়ে sort (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!")

কোডের প্রতিটি অংশ

• if not intervals: return [] — খালি ইনপুটে আগেভাগে খালি list ফেরত, পরের intervals[0] যেন crash না করে।
• intervals.sort(key=lambda iv: iv[0]) — start দিয়ে সাজাও; এতেই overlap-রা পাশাপাশি বসে (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।

Output মিলিয়ে দেখা

[[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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

• 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 এড়ানো যায়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• Insert Interval (একটা নতুন interval ঢুকিয়ে আবার merge) — https://leetcode.com/problems/insert-interval/
• Non-overlapping Intervals (সবচেয়ে কম interval সরিয়ে overlap মুক্ত করা) — https://leetcode.com/problems/non-overlapping-intervals/
• Meeting Rooms II (heap + intervals, একসাথে সর্বোচ্চ কতগুলো) — https://leetcode.com/problems/meeting-rooms-ii/
• Interval List Intersections (দুই sorted list-এর overlap বের করা) — https://leetcode.com/problems/interval-list-intersections/

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।