Problem link ও উৎস
- **Original source:** LeetCode Non-overlapping Intervals + CSES Movie Festival
- **Platform:** LeetCode —
, CSES Movie Festival —
- **Topic:** Greedy math tricks → interval scheduling, exchange argument
- **Difficulty:** Medium
- **Pattern:** earliest finish first (শেষ-সময় দিয়ে sort করে greedy)
- **Basic idea inherited from:** — (exchange-argument greedy-র প্রথম পরিষ্কার উদাহরণ)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কয়েকটা কাজ (বা সিনেমা, বা মিটিং) আছে, প্রত্যেকটার একটা শুরুর সময় `start` আর শেষ সময় `end`। তুমি একসাথে একটার বেশি করতে পারো না — দুটো কাজের সময় overlap করলে যেকোনো একটাই নিতে পারবে।
প্রশ্ন: **সর্বোচ্চ কয়টা কাজ** (পরস্পর overlap না করে) করতে পারবে?
(ঘনিষ্ঠ সংস্করণ — Non-overlapping Intervals: **সর্বনিম্ন কয়টা interval বাদ দিলে** বাকিগুলো overlap-মুক্ত হয়। দুটো আসলে একই মুদ্রার দুই পিঠ: `বাদ = মোট − সর্বোচ্চ রাখা`।)
### Input ও output {#6-example-input-and-output}
```text
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 ভেদে এই নিয়ম বদলালে তুলনায় `>` বনাম `≥` পাল্টাতে হয়।)
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটাই হলঘরে আজ অনেকগুলো ইভেন্ট হতে চায়, প্রত্যেকের নির্দিষ্ট শুরু-শেষ সময়। তুমি যত বেশি সম্ভব ইভেন্ট ঢোকাতে চাও।
স্বাভাবিক লোভ হতে পারে "সবচেয়ে আগে শুরু হওয়াটা নাও" — কিন্তু সেটা যদি ভোর থেকে রাত পর্যন্ত চলা একটা লম্বা ইভেন্ট হয়, পুরো দিন খেয়ে ফেলবে! বুদ্ধিমানের লোভ: **"সবচেয়ে আগে শেষ হওয়াটা নাও।"** যে তাড়াতাড়ি হল ছেড়ে দেয়, সে পরের জনের জন্য সবচেয়ে বেশি সময় রেখে যায়। বারবার "এই মুহূর্তে যে সবার আগে শেষ হয়" বেছে নিলে দিনে সবচেয়ে বেশি ইভেন্ট আঁটে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা exchange-argument greedy-র প্রথম পরিষ্কার উদাহরণ, তাই আগের কোনো greedy-র উপর সরাসরি দাঁড়ায় না (`inherited from: —`)।
তবে এর হাতিয়ার দুটো চেনা: **sorting** (level জুড়ে বারবার) আর একটা **"শেষ নেওয়া কাজের end" track করা** (এক সংখ্যা মনে রাখা, ঠিক 104-এর furthest-এর মতো)। নতুনত্ব হলো প্রমাণের ধরন — concept-notes-এর exchange argument এখানে হাতে-কলমে প্রয়োগ হয়।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল idea — **earliest finish first**: কাজগুলো **শেষ হওয়ার সময় (end) দিয়ে sort করো**, তারপর বাঁ থেকে ডানে যেটা আগের নেওয়া কাজের সাথে overlap করে না সেটাই নাও।
কেন শেষ-সময়? — কারণ যে কাজ সবচেয়ে আগে শেষ হয়, সে **সবচেয়ে বেশি ফাঁকা সময়** রেখে যায় পরের কাজের জন্য। লোভটা এখানে "তাড়াতাড়ি মুক্ত হও"।
(সাবধান: "earliest **start**" বা "shortest duration" দিয়ে sort করলে greedy **ভুল** হয় — section 17-এ counterexample।)
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সরাসরি, কিন্তু ধীর — **সব 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
```
প্রতিটা সম্ভাব্য সংগ্রহ দেখে বলে এটা সবসময় সঠিক — আমাদের যাচাইয়ের মাপকাঠি।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
n টা interval-এর subset আছে **2ⁿ** — তাই এই brute force exponential। n = 20 হলেই 10 লক্ষেরও বেশি subset, আর বড় n-এ একেবারে অসম্ভব।
```text
সব subset = 2ⁿ → exponential বিস্ফোরণ
brute force : O(2ⁿ · ...) (ধীর)
greedy : O(n log n) (শুধু sort + এক pass — earliest finish)
```
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল 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-এ।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
এক লাইনের "আহা!":
> "সবচেয়ে আগে যেটা শেষ হয়, সেটা পরের জনের জন্য সবচেয়ে বেশি ফাঁকা রেখে যায় — তাই end দিয়ে sort করো, start নয়।"
স্বাভাবিক প্রবৃত্তি "আগে শুরু হওয়াটা নাও" — সেটা ছেড়ে "আগে শেষ হওয়াটা নাও"-এ যাওয়াই tweak। আর কেবল একটা সংখ্যা (`last_end`) মনে রাখলেই overlap চেক হয়ে যায়।
### ছবিতে বোঝা {#5-visual-explanation}
intervals `[(1,3), (2,5), (4,7), (6,8)]` — end দিয়ে sort করে greedy:
```text
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-এর ছবি):
```text
greedy: [--g--] (সবচেয়ে আগে শেষ)
optimal: [-----j-----] (অন্য কেউ আগে নিয়েছিল)
g আগে শেষ ⇒ j-এর পরের যা কিছু নেওয়া যেত, g-এর পরেও নেওয়া যায়
⇒ optimal-এ j-কে g দিয়ে বদলালে সংখ্যা কমে না — তাই g নেওয়া নিরাপদ।
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
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` যতটা সম্ভব ছোট থেকে পরের জনের জন্য জায়গা রাখল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
intervals = sorted(intervals, key=lambda x: x[1])
```
greedy-র প্রাণ — **end (x[1]) দিয়ে sort**। এতে সবচেয়ে আগে শেষ হওয়া কাজ সবার আগে আসে।
```text
last_end = float("-inf")
```
এখনো কিছু নিইনি, তাই "শেষ নেওয়া কাজের end" কে সবচেয়ে ছোট ধরে নিই।
```text
for s, e in intervals:
if s >= last_end:
count += 1
last_end = e
```
প্রতিটা কাজে দেখি — এর শুরু `s` কি আগের নেওয়া কাজের শেষের পরে/সমান? হলে overlap নেই, নিই, আর `last_end` আপডেট করি। এই একটা সংখ্যা (`last_end`)-ই পুরো overlap-চেক সামলায়।
```text
return len(intervals) - max_intervals(intervals) # min_removals
```
মোট থেকে সর্বোচ্চ রাখা বাদ দিলেই সর্বনিম্ন বাদ-সংখ্যা — দুই problem এক সূত্রে বাঁধা।
`max_intervals_brute` সব subset দেখে নির্ভুল উত্তর দেয়; এখানে random ছোট interval-set বানিয়ে greedy আর brute মিলিয়ে দেখা হয়েছে (seed fixed, তাই প্রতিবার একই)।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে ছাপবে:
```text
2
3
1
সব test pass!
```
প্রথম তিন line `print` থেকে: প্রথম set-এ সর্বোচ্চ 2টা রাখা যায়; দ্বিতীয়টায় touch-করা 3টাই রাখা যায়; তৃতীয়টায় লম্বা interval-টা বাদ দিতে হয় (min removal 1)। তার আগে সব `assert` (সরাসরি case + 400টা random ছোট set) চুপচাপ pass করেছে, তাই শেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n log n)** — মূল খরচ sorting; তারপর এক pass O(n)। brute force-এর O(2ⁿ) থেকে আকাশ-পাতাল উন্নতি।
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(n)** (বা sort in-place হলে O(1)–O(log n) বাড়তি) — শুধু sorted তালিকা আর গুটিকয় variable; আলাদা বড় structure লাগে না।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
- **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 এমনিতেই সামলায়, তবু খেয়াল রাখো।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Non-overlapping Intervals** (