dsa / dsa-hashing
20 mins
DSA Module 12: Greedy Choice Optimization
Why This Matters: Greedy algorithms make locally optimal choices at each step to reach a global optimum.
## Greedy Interval Selection
Sorting intervals by end time guarantees maximal non-overlapping selections.
```python
def max_intervals(intervals: list[list[int]]) -> int:
intervals.sort(key=lambda x: x[1]) # Sort by end time
count, end = 0, float('-inf')
for inv in intervals:
if inv[0] >= end:
count += 1
end = inv[1]
return count
```
MENTAL MODEL & MEMORY LAYOUT
GREEDY CHOICE PROPERTY: Sort intervals by END TIME ──► Always pick earliest ending interval ──► Leaves max remaining space!
COMMON PITFALLS TO AVOID
- Sorting by start time instead of end time in interval scheduling.
Interval Selection Pattern
intervals = [[1, 2], [2, 3], [3, 4]] # Pick [1,2], then [2,3], then [3,4] => Max 3 intervals
Selecting interval ending earliest leaves maximum remaining time.
CONCEPT MASTERY CHECKPOINT
In Interval Scheduling, why do we sort intervals by END time?
NEXT RECOMMENDED LESSON
DSA Module 13: Dynamic Programming
Challenge: Count non-overlapping intervals selected by end time.