Interval Scheduling and Merging
Solve meeting-rooms and non-overlapping-intervals by sorting on end time, and merge-intervals by sorting on start time.
Interval Problems Overview
Interval problems appear constantly in scheduling, calendar management, and resource allocation interviews. The key patterns are: merge overlapping intervals, count minimum meeting rooms, find maximum non-overlapping set, and insert a new interval. Most interval problems start with the same step: sort intervals by start time (or end time, depending on the problem). Getting the sorting key right is often the hardest part.
# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3] |-|
# [2,6] |---|
# [8,10] |--|
# [15,18] |---|
print('Intervals ready for analysis')Merge Overlapping Intervals
Merge Intervals (LeetCode 56): given a list of intervals, merge all overlapping ones. Algorithm: sort by start time. Walk through the sorted list; if the current interval overlaps with the last merged interval (its start ≤ last merged end), extend the last merged interval's end to the max of both ends. Otherwise, append the current interval as a new merged interval. Time: O(n log n) for sorting, O(n) for merging.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping: extend the last interval
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: add as new interval
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)All lessons in this course
- Greedy vs DP: When to Use Each
- Interval Scheduling and Merging
- Jump Game I and II
- Task Scheduler and Gas Station