Lesson 2 — Intermediate

Interval Scheduling & Merge Intervals

Interval problems interview mein bahut puchhe jaate hain — merge karo, insert karo, overlap count karo. Inhe solve karne ka ek pattern hai: sort by start time, phir iterate karo.

Merge Intervals Pattern

Socho tumhare paas meetings hain calendar mein. Agar do meetings overlap karti hain toh unhe merge karna padega — ek badi meeting ban jayegi. Yehi Merge Intervals problem hai.

Pattern simple hai:

1. Intervals ko start time ke hisaab se sort karo.
2. Pehli interval ko result mein daalo.
3. Baaki intervals ke liye check karo — agar current interval previous ke andar start ho rahi hai (overlap hai), toh merge karo. Nahi toh nayi interval add karo.

Overlap check: Agar current_start <= previous_end hai toh overlap hai. Merge mein max(previous_end, current_end) lete hain.

Visual: Merge Intervals

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

Sorted by start:
 [1,3] ——————
 [2,6] ———————— ✓ Overlap! Merge to [1,6]
 [8,10] ———— ✓ No overlap, new group
 [15,18] ——————

Step-by-step:
 result = [[1,3]]
 [2,6]: 2 <= 3 ✓ merge ✓ result = [[1,6]]
 [8,10]: 8 > 6 ✓ new ✓ result = [[1,6], [8,10]]
 [15,18]: 15 > 10 ✓ new ✓ result = [[1,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Insert Interval

Ek nayi interval di gayi hai — use existing merged intervals mein insert karo aur phir se merge karo. Yeh thoda tricky hai kyunki 3 cases hote hain:

• Case 1: Nayi interval current interval se pehle khatam ho rahi hai — pehle add karo nayi, phir baaki.
• Case 2: Nayi interval current interval ke baad start ho rahi hai — current add karo, baad mein nayi ayegi.
• Case 3: Overlap hai — merge karo aur end time update karo.

Non-Overlapping Intervals

Problem: Minimum kitne intervals remove karo taaki koi overlap na ho✓ Yeh Activity Selection ka reverse hai.

Greedy approach: End time ke hisaab se sort karo, aur har baar sabse pehle khatam hone wali interval select karo. Jo overlap kare use remove karo. Count of removed = total - selected.

Code: Merge Intervals

def merge(intervals):
 # Step 1: Sort by start time
 intervals.sort()

 # Step 2: Pehli interval result mein daalo
 merged = [intervals[0]]

 # Step 3: Baaki intervals process karo
 for start, end in intervals[1:]:
 # Agar current interval previous ke andar hai
 if start <= merged[-1][1]:
 # Merge karo — end time update karo
 merged[-1][1] = max(merged[-1][1], end)
 else:
 # No overlap — nayi interval add karo
 merged.append([start, end])

 return merged


# Example
intervals = [[1,3], [2,6], [8,10], [15,18]]
print(merge(intervals))
# Output: [[1,6], [8,10], [15,18]]

Code: Insert Interval

def insert(intervals, newInterval):
 result = []
 i = 0
 n = len(intervals)

 # Jo intervals newInterval se pehle hain — unhe add karo
 while i < n and intervals[i][1] < newInterval[0]:
 result.append(intervals[i])
 i += 1

 # Jo intervals overlap karti hain — merge karo
 while i < n and intervals[i][0] <= newInterval[1]:
 newInterval[0] = min(newInterval[0], intervals[i][0])
 newInterval[1] = max(newInterval[1], intervals[i][1])
 i += 1
 result.append(newInterval)

 # Jo baaki intervals hain — unhe add karo
 while i < n:
 result.append(intervals[i])
 i += 1

 return result

Try it: code khud likho

Common Mistakes

• Sort na karna — Bina sort ke iterate karna sabse bada mistake hai. Hamesha pehle sort karo.
• End time update karte waqt max na lena — Merge karte waqt max(old_end, new_end) lena zaroori hai. Sirf new_end lena galat hai agar previous end bada ho.
• Insert interval mein edge cases — Empty intervals list, nayi interval sabse pehle ya sabse baad aani chahiye — handle karo.
• Overlap ka definition galat samajhna — [1,2] aur [2,3] overlap nahi karti (touch karti hain). [1,3] aur [2,4] overlap karti hain.
• In-place modify karna — Interview mein poochho ki modify karna hai ya naya list banana hai. In-place mein indexing tricky ho sakti hai.