Interval merging is a common algorithmic problem that appears frequently in scheduling, calendar applications, and resource allocation systems. The core challenge is determining when two intervals overlap and how to combine them efficiently.
Two intervals overlap when they share at least one point in common. For intervals [a, b] and [c, d], they overlap if the start of one interval is less than or equal to the end of the other. The key insight is that after sorting intervals by their start times, we only need to compare each interval with the previously processed one.
The algorithm follows a greedy approach: sort the intervals first, then iterate through them while maintaining a result list. For each interval, we check if it overlaps with the last interval in our result. If it does, we merge them by extending the end time. If not, we add it as a separate interval.
This approach is efficient because sorting gives us a guarantee that we'll encounter intervals in the correct order to make optimal merging decisions. The time complexity is O(n log n) due to sorting, and the space complexity is O(n) for the result.
Interval problems teach us about the power of sorting as a preprocessing step and how greedy algorithms can solve complex-seeming problems with simple, local decisions.
1# Example: Check if two intervals overlap
2def intervals_overlap(interval1, interval2):
3 start1, end1 = interval1
4 start2, end2 = interval2
5
6 # They overlap if one starts before the other ends
7 return start1 <= end2 and start2 <= end1
8
9# Test overlapping
10print(intervals_overlap([1, 3], [2, 5])) # True - they overlap from 2 to 3
11print(intervals_overlap([1, 2], [3, 4])) # False - no overlap
12print(intervals_overlap([1, 3], [3, 5])) # True - they touch at point 3