1. One-Liner
Interval scheduling picks the maximum number of compatible intervals on a timeline by repeatedly taking the interval with the earliest finishing end among those that start after the last pick.
2. The Problem It Solves
Each interval [l, r] uses a resource exclusively. Maximize how many intervals you can schedule without overlap (unweighted).
3. The Core Idea
End-time ordering frees the resource as soon as possible for the rest of the day—same structural insight as activity selection, phrased in interval language for timelines and calendars.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Sort | By right endpoint r ascending |
| 2. Greedy | Take first; set end = r |
| 3. Scan | Next interval with l ≥ end |
| 4. Count | Iterate until list ends |
5. Dry Run Example
Intervals [1,3], [2,4], [3,6], [5,7] → sorted ends choose [1,3], [3,6], [5,7] careful check non-overlap → typical max is 3 or 2 depending on ties; algorithm respects l ≥ lastEnd.
6. Key Properties
| Property | Value |
|---|---|
| Greedy proof | Exchange on finish times |
| Ties | Same end—either safe with consistent rule |
7. Where It Is Used
| Domain | Use |
|---|---|
| Calendars | Max meetings in one room |
| Theory | Intro to greedy scheduling |
8. Interview Tips
Relate to activity selection; distinguish weighted intervals → DP; mention interval graphs.
9. Comparison with Other Approaches
| Problem | Technique |
|---|---|
| Max count | Greedy by end |
| Max weight | DP on sorted intervals |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n log n) |
| Space | O(n) or O(1) extra |
Implementation Example (PYTHON)
def max_intervals(intervals):
# intervals: list of (l, r)
intervals.sort(key=lambda x: x[1])
cnt = 0
last = float('-inf')
for l, r in intervals:
if l >= last:
cnt += 1
last = r
return cnt