01
Interval Scheduling
Chapter 1 • Intermediate
90 min
Interval Scheduling
Problem Statement
Given a set of intervals, select the maximum number of non-overlapping intervals.
Input: Intervals [(start_i, end_i), ...]
Output: Maximum number of non-overlapping intervals
Greedy Strategy
Strategy 1: Earliest Finish Time
Algorithm:
- Sort intervals by finish time
- Select first interval
- For each remaining interval:
- If it doesn't overlap with last selected, select it
Why it works: Selecting earliest finish time leaves maximum room for future intervals.
Implementation
python.js
def interval_scheduling(intervals):
"""
Maximum non-overlapping intervals using greedy.
Time: O(n log n), Space: O(1)
"""
if not intervals:
return []
# Sort by finish time
intervals.sort(key=lambda x: x[1])
selected = [intervals[0]]
last_finish = intervals[0][1]
for start, finish in intervals[1:]:
if start >= last_finish: # No overlap
selected.append((start, finish))
last_finish = finish
return selected
Weighted Interval Scheduling
When intervals have weights, we want to maximize total weight.
Dynamic Programming Approach
python.js
def weighted_interval_scheduling(intervals):
"""
Maximum weight non-overlapping intervals.
intervals: [(start, end, weight), ...]
Time: O(n log n), Space: O(n)
"""
n = len(intervals)
intervals.sort(key=lambda x: x[1]) # Sort by finish time
# Find latest non-overlapping interval for each interval
prev = [-1] * n
for i in range(n):
start_i = intervals[i][0]
# Binary search for latest interval with finish <= start_i
left, right = 0, i - 1
while left <= right:
mid = (left + right) // 2
if intervals[mid][1] <= start_i:
prev[i] = mid
left = mid + 1
else:
right = mid - 1
# DP: dp[i] = max weight using intervals 0..i
dp = [0] * n
dp[0] = intervals[0][2]
for i in range(1, n):
# Option 1: Don't include interval i
weight1 = dp[i-1]
# Option 2: Include interval i
weight2 = intervals[i][2]
if prev[i] != -1:
weight2 += dp[prev[i]]
dp[i] = max(weight1, weight2)
return dp[n-1]
Activity Selection Problem
Classic problem: Select maximum activities that can be performed.
python.js
def activity_selection(activities):
"""
Select maximum activities.
activities: [(start, end), ...]
"""
activities.sort(key=lambda x: x[1]) # Sort by end time
selected = [activities[0]]
last_end = activities[0][1]
for start, end in activities[1:]:
if start >= last_end:
selected.append((start, end))
last_end = end
return selected
Practice Problems
- Maximum non-overlapping intervals
- Weighted interval scheduling
- Activity selection with constraints
- Interval partitioning (minimum rooms)
- Merge overlapping intervals