107 — Interval Scheduling¶

এই problem-টা পুরো level-এর হৃদয় — কারণ এখানেই exchange argument সবচেয়ে পরিষ্কারভাবে দেখা যায়। "সবচেয়ে আগে যেটা শেষ হয়, সেটা আগে নাও" — এই এক লাইনের greedy, আর তার পেছনে এক লাইনের প্রমাণ। ধীরে পড়ো; এটা ভালো করে বুঝলে interviewer-এর "why does this work?" প্রশ্নে তুমি হাসিমুখে উত্তর দেবে।

Problem link ও উৎস

Original source: LeetCode Non-overlapping Intervals + CSES Movie Festival
Platform: LeetCode — https://leetcode.com/problems/non-overlapping-intervals/, CSES Movie Festival — https://cses.fi/problemset/task/1629
Topic: Greedy math tricks → interval scheduling, exchange argument
Difficulty: Medium
Pattern: earliest finish first (শেষ-সময় দিয়ে sort করে greedy)
Basic idea inherited from: — (exchange-argument greedy-র প্রথম পরিষ্কার উদাহরণ)

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

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

কয়েকটা কাজ (বা সিনেমা, বা মিটিং) আছে, প্রত্যেকটার একটা শুরুর সময় start আর শেষ সময় end। তুমি একসাথে একটার বেশি করতে পারো না — দুটো কাজের সময় overlap করলে যেকোনো একটাই নিতে পারবে।

প্রশ্ন: সর্বোচ্চ কয়টা কাজ (পরস্পর overlap না করে) করতে পারবে?

(ঘনিষ্ঠ সংস্করণ — Non-overlapping Intervals: সর্বনিম্ন কয়টা interval বাদ দিলে বাকিগুলো overlap-মুক্ত হয়। দুটো আসলে একই মুদ্রার দুই পিঠ: বাদ = মোট − সর্বোচ্চ রাখা।)

Input ও output¶

উদাহরণ

intervals                          ->  max রাখা  /  min বাদ
-------------------------------------------------------------------
[(1,3),(2,5),(4,7),(6,8)]          ->  2  রাখা   /  2  বাদ
[(1,2),(2,3),(3,4)]                ->  3  রাখা   /  0  বাদ   (touch overlap নয়)
[(1,100),(2,3),(4,5)]              ->  2  রাখা   /  1  বাদ   (লম্বাটা বাদ)
[]                                  ->  0  রাখা   /  0  বাদ
[(5,6)]                            ->  1  রাখা   /  0  বাদ

এখানে আমরা ধরছি end == পরের start হলে overlap নয় (একটা শেষ হলেই পরেরটা শুরু হতে পারে) — [(1,2),(2,3)] দুটোই রাখা যায়। (Problem ভেদে এই নিয়ম বদলালে তুলনায় > বনাম ≥ পাল্টাতে হয়।)

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

ভাবো একটাই হলঘরে আজ অনেকগুলো ইভেন্ট হতে চায়, প্রত্যেকের নির্দিষ্ট শুরু-শেষ সময়। তুমি যত বেশি সম্ভব ইভেন্ট ঢোকাতে চাও।

স্বাভাবিক লোভ হতে পারে "সবচেয়ে আগে শুরু হওয়াটা নাও" — কিন্তু সেটা যদি ভোর থেকে রাত পর্যন্ত চলা একটা লম্বা ইভেন্ট হয়, পুরো দিন খেয়ে ফেলবে! বুদ্ধিমানের লোভ: "সবচেয়ে আগে শেষ হওয়াটা নাও।" যে তাড়াতাড়ি হল ছেড়ে দেয়, সে পরের জনের জন্য সবচেয়ে বেশি সময় রেখে যায়। বারবার "এই মুহূর্তে যে সবার আগে শেষ হয়" বেছে নিলে দিনে সবচেয়ে বেশি ইভেন্ট আঁটে।

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

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

এটা exchange-argument greedy-র প্রথম পরিষ্কার উদাহরণ, তাই আগের কোনো greedy-র উপর সরাসরি দাঁড়ায় না (inherited from: —)।

তবে এর হাতিয়ার দুটো চেনা: sorting (level জুড়ে বারবার) আর একটা "শেষ নেওয়া কাজের end" track করা (এক সংখ্যা মনে রাখা, ঠিক 104-এর furthest-এর মতো)। নতুনত্ব হলো প্রমাণের ধরন — concept-notes-এর exchange argument এখানে হাতে-কলমে প্রয়োগ হয়।

ভেতরের অঙ্ক¶

মূল idea — earliest finish first: কাজগুলো শেষ হওয়ার সময় (end) দিয়ে sort করো, তারপর বাঁ থেকে ডানে যেটা আগের নেওয়া কাজের সাথে overlap করে না সেটাই নাও।

কেন শেষ-সময়? — কারণ যে কাজ সবচেয়ে আগে শেষ হয়, সে সবচেয়ে বেশি ফাঁকা সময় রেখে যায় পরের কাজের জন্য। লোভটা এখানে "তাড়াতাড়ি মুক্ত হও"।

(সাবধান: "earliest start" বা "shortest duration" দিয়ে sort করলে greedy ভুল হয় — section 17-এ counterexample।)

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

প্রথম সরল উপায়¶

সরাসরি, কিন্তু ধীর — সব subset চেষ্টা করো। প্রতিটা interval-এর সংগ্রহ নাও, দেখো সেটা overlap-মুক্ত কিনা, আর সবচেয়ে বড় overlap-মুক্ত সংগ্রহের আকার রাখো:

Python

from itertools import combinations

def max_intervals_brute(intervals):
    n = len(intervals)
    best = 0
    for k in range(n + 1):
        for combo in combinations(intervals, k):
            s = sorted(combo, key=lambda x: x[0])
            ok = all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1))
            if ok:
                best = max(best, k)
    return best

প্রতিটা সম্ভাব্য সংগ্রহ দেখে বলে এটা সবসময় সঠিক — আমাদের যাচাইয়ের মাপকাঠি।

কোথায় বেশি কাজ হতে পারে¶

n টা interval-এর subset আছে 2ⁿ — তাই এই brute force exponential। n = 20 হলেই 10 লক্ষেরও বেশি subset, আর বড় n-এ একেবারে অসম্ভব।

উদাহরণ

সব subset = 2ⁿ → exponential বিস্ফোরণ

brute force : O(2ⁿ · ...)  (ধীর)
greedy      : O(n log n)   (শুধু sort + এক pass — earliest finish)

আরও ভালোভাবে ভাবা¶

মূল observation: সবচেয়ে আগে শেষ হওয়া কাজ নেওয়া কখনো ভুল হতে পারে না। তাই end দিয়ে sort করে এক pass:

Python

def max_intervals(intervals):
    intervals = sorted(intervals, key=lambda x: x[1])   # end দিয়ে sort
    count = 0
    last_end = float("-inf")
    for s, e in intervals:
        if s >= last_end:        # আগের নেওয়া কাজের পরে শুরু → overlap নেই
            count += 1
            last_end = e
    return count


def min_removals(intervals):
    """Non-overlapping Intervals: কয়টা বাদ দিলে বাকি overlap-মুক্ত।"""
    return len(intervals) - max_intervals(intervals)

Greedy choice: অবশিষ্ট কাজগুলোর মধ্যে যেটা সবচেয়ে আগে শেষ হয়, সেটাই নাও।

কেন কাজ করে (exchange argument, এক লাইন): ধরো কোনো optimal solution-এর প্রথম কাজ j, আর greedy নিয়েছে সবচেয়ে আগে শেষ হওয়া g (finish(g) ≤ finish(j)); j-কে g দিয়ে বদলে দিলে g আগে শেষ হওয়ায় বাকি সব কাজ আগের মতোই বসে — solution-এর আকার কমে না, তাই greedy-র প্রথম choice নিরাপদ, আর বাকিটা একই যুক্তি ছোট problem-এ।

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

এক লাইনের "আহা!":

"সবচেয়ে আগে যেটা শেষ হয়, সেটা পরের জনের জন্য সবচেয়ে বেশি ফাঁকা রেখে যায় — তাই end দিয়ে sort করো, start নয়।"

স্বাভাবিক প্রবৃত্তি "আগে শুরু হওয়াটা নাও" — সেটা ছেড়ে "আগে শেষ হওয়াটা নাও"-এ যাওয়াই tweak। আর কেবল একটা সংখ্যা (last_end) মনে রাখলেই overlap চেক হয়ে যায়।

ছবিতে বোঝা¶

intervals [(1,3), (2,5), (4,7), (6,8)] — end দিয়ে sort করে greedy:

উদাহরণ

time:  1   2   3   4   5   6   7   8
A:     [-------)                         (1,3)  end=3
B:         [-----------)                 (2,5)  end=5
C:                 [-----------)         (4,7)  end=7
D:                         [-------)     (6,8)  end=8

end দিয়ে sort: A(3), B(5), C(7), D(8)

নাও A (end=3)। B শুরু 2 < 3 → overlap, বাদ।
C শুরু 4 ≥ 3 → নাও (end=7)। D শুরু 6 < 7 → overlap, বাদ।
বাছাই: A, C → সর্বোচ্চ 2টা।

কেন earliest finish নিরাপদ (exchange argument-এর ছবি):

উদাহরণ

greedy:   [--g--]              (সবচেয়ে আগে শেষ)
optimal:     [-----j-----]     (অন্য কেউ আগে নিয়েছিল)

g আগে শেষ ⇒ j-এর পরের যা কিছু নেওয়া যেত, g-এর পরেও নেওয়া যায়
⇒ optimal-এ j-কে g দিয়ে বদলালে সংখ্যা কমে না — তাই g নেওয়া নিরাপদ।

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

intervals [(1,3), (2,5), (4,7), (6,8)] ধীরে চালাই। end দিয়ে sort করলে ক্রম একই: (1,3), (2,5), (4,7), (6,8)।

interval (s, e)	s ≥ last_end?	নিলাম?	count	last_end
শুরু	—	—	0	-∞
(1, 3)	1 ≥ -∞ হ্যাঁ	নিলাম	1	3
(2, 5)	2 ≥ 3 না	বাদ	1	3
(4, 7)	4 ≥ 3 হ্যাঁ	নিলাম	2	7
(6, 8)	6 ≥ 7 না	বাদ	2	7

সর্বোচ্চ রাখা = 2 (A আর C); বাদ = 4 − 2 = 2। লক্ষ করো — প্রতিবার "আগে শেষ হওয়াটা" নেওয়ায় last_end যতটা সম্ভব ছোট থেকে পরের জনের জন্য জায়গা রাখল।

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

Python¶

Python

def max_intervals(intervals):
    """earliest finish first — সর্বোচ্চ কয়টা overlap-মুক্ত interval রাখা যায়।"""
    intervals = sorted(intervals, key=lambda x: x[1])   # end দিয়ে sort
    count = 0
    last_end = float("-inf")
    for s, e in intervals:
        if s >= last_end:
            count += 1
            last_end = e
    return count


def min_removals(intervals):
    """Non-overlapping Intervals: কয়টা বাদ দিলে বাকি overlap-মুক্ত।"""
    return len(intervals) - max_intervals(intervals)


def max_intervals_brute(intervals):
    """সব subset দেখে সর্বোচ্চ overlap-মুক্ত — ধীর কিন্তু নির্ভুল (যাচাই)।"""
    from itertools import combinations
    n = len(intervals)
    best = 0
    for k in range(n + 1):
        for combo in combinations(intervals, k):
            s = sorted(combo, key=lambda x: x[0])
            ok = all(s[i][1] <= s[i + 1][0] for i in range(len(s) - 1))
            if ok:
                best = max(best, k)
    return best


# --- ছোট test (সব pass করা উচিত) ---
assert max_intervals([(1, 3), (2, 5), (4, 7), (6, 8)]) == 2
assert max_intervals([(1, 2), (2, 3), (3, 4)]) == 3        # touch = overlap নয়
assert max_intervals([(1, 100), (2, 3), (4, 5)]) == 2      # লম্বাটা বাদ
assert max_intervals([]) == 0
assert max_intervals([(5, 6)]) == 1
assert min_removals([(1, 100), (2, 3), (4, 5)]) == 1

# greedy আর brute force ছোট সব interval-set-এ একমত (brute = সত্য)
import itertools, random
random.seed(0)
for _ in range(400):
    n = random.randint(0, 6)
    ivs = []
    for _ in range(n):
        a = random.randint(0, 6)
        b = random.randint(a + 1, a + 6)
        ivs.append((a, b))
    assert max_intervals(ivs) == max_intervals_brute(ivs)

print(max_intervals([(1, 3), (2, 5), (4, 7), (6, 8)]))   # 2
print(max_intervals([(1, 2), (2, 3), (3, 4)]))           # 3
print(min_removals([(1, 100), (2, 3), (4, 5)]))          # 1
print("সব test pass!")

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

উদাহরণ

intervals = sorted(intervals, key=lambda x: x[1])

greedy-র প্রাণ — end (x[1]) দিয়ে sort। এতে সবচেয়ে আগে শেষ হওয়া কাজ সবার আগে আসে।

উদাহরণ

last_end = float("-inf")

এখনো কিছু নিইনি, তাই "শেষ নেওয়া কাজের end" কে সবচেয়ে ছোট ধরে নিই।

উদাহরণ

for s, e in intervals:
    if s >= last_end:
        count += 1
        last_end = e

প্রতিটা কাজে দেখি — এর শুরু s কি আগের নেওয়া কাজের শেষের পরে/সমান? হলে overlap নেই, নিই, আর last_end আপডেট করি। এই একটা সংখ্যা (last_end)-ই পুরো overlap-চেক সামলায়।

উদাহরণ

return len(intervals) - max_intervals(intervals)   # min_removals

মোট থেকে সর্বোচ্চ রাখা বাদ দিলেই সর্বনিম্ন বাদ-সংখ্যা — দুই problem এক সূত্রে বাঁধা।

max_intervals_brute সব subset দেখে নির্ভুল উত্তর দেয়; এখানে random ছোট interval-set বানিয়ে greedy আর brute মিলিয়ে দেখা হয়েছে (seed fixed, তাই প্রতিবার একই)।

Output মিলিয়ে দেখা¶

চালালে ছাপবে:

উদাহরণ

2
3
1
সব test pass!

প্রথম তিন line print থেকে: প্রথম set-এ সর্বোচ্চ 2টা রাখা যায়; দ্বিতীয়টায় touch-করা 3টাই রাখা যায়; তৃতীয়টায় লম্বা interval-টা বাদ দিতে হয় (min removal 1)। তার আগে সব assert (সরাসরি case + 400টা random ছোট set) চুপচাপ pass করেছে, তাই শেষে সব test pass!।

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

সময়¶

O(n log n) — মূল খরচ sorting; তারপর এক pass O(n)। brute force-এর O(2ⁿ) থেকে আকাশ-পাতাল উন্নতি।

অতিরিক্ত জায়গা¶

O(n) (বা sort in-place হলে O(1)–O(log n) বাড়তি) — শুধু sorted তালিকা আর গুটিকয় variable; আলাদা বড় structure লাগে না।

যে ভুলগুলো এড়াতে হবে¶

start দিয়ে sort করা — সবচেয়ে কমন ভুল। [(1, 100), (2, 3), (4, 5)]-এ start দিয়ে sort করে প্রথমটা নিলে (1,100) পুরো সময় খেয়ে ফেলে → মাত্র 1; অথচ end দিয়ে করলে (2,3),(4,5) → 2।
shortest duration দিয়ে sort করা — এটাও ভুল; ছোট একটা কাজ মাঝখানে বসে দুটো বড় কাজকে আটকে দিতে পারে। প্রমাণিত সঠিক একমাত্র earliest finish।
> বনাম ≥ গুলিয়ে ফেলা — end == পরের start overlap কিনা তা problem-এর নিয়মে নির্ভর; এখানে আমরা "touch = overlap নয়" ধরেছি (s >= last_end)। নিয়ম উল্টো হলে > ব্যবহার করো।
max রাখা আর min বাদ গুলিয়ে ফেলা — min বাদ = মোট − max রাখা; কোনটা চাওয়া হয়েছে আগে নিশ্চিত হও।
খালি list না সামলানো — intervals ফাঁকা হলে উত্তর 0; loop এমনিতেই সামলায়, তবু খেয়াল রাখো।

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

এই ধারণার পরের অনুশীলন¶

LeetCode — Non-overlapping Intervals (https://leetcode.com/problems/non-overlapping-intervals/) — সরাসরি "min removal" রূপ; মোট − max রাখা।
CSES — Movie Festival (https://cses.fi/problemset/task/1629) — হুবহু "max non-overlapping" greedy।
LeetCode — Minimum Number of Arrows to Burst Balloons (https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/) — একই earliest-finish greedy, একটু ছদ্মবেশে (overlap group গোনা)।

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

Earliest finish first (interval scheduling) — কাজ end দিয়ে sort করো, এক সংখ্যা last_end ধরে রাখো, overlap না করলে নাও; exchange argument বলে এটা optimal। বড় শিক্ষা: interval নিয়ে "সর্বোচ্চ কয়টা" চাইলে — শেষ-সময় দিয়ে sort, শুরু-সময় নয়।

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

ভবিষ্যতের আমাকে এক লাইনে: "Interval scheduling = earliest finish first; end দিয়ে sort, last_end track করে overlap-মুক্ত যা পারো নাও। প্রমাণ = exchange argument (আগে শেষ হওয়া কাজ সবচেয়ে বেশি জায়গা রাখে)। start দিয়ে sort করলে ভুল।"

পরের ধাপ → 108 — Minimum Platforms (level 5-এর sweep line ফিরে এলো — event sweep)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

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