Intervals
This page covers problems involving intervals, which are given as a list of [start, end] times.
Interval problems typically involve sorting the given intervals, and then processing each interval in sorted each order. On this page, we'll cover:
- Sorting intervals by start time
- Sorting intervals by end time
Sorting by Start Time
Sorting intervals by their start times makes it easy to merge two intervals that are overlapping.
Overlapping Intervals
After sorting by start time, an interval overlaps with the previous interval if it starts before the end time of the previous interval.
Detecting overlapping intervals is the basis of the question Can Attend Meetings, in which we are given a list of intervals representing the start and end times of meetings, and we need to determine if a person can attend all meetings.
We sort the intervals by their start times and iterate over each meeting. If the current meeting overlaps with the previous one, we return False. If we make it through the entire list without finding any overlaps, we return True.
def canAttendMeetings(intervals):intervals.sort(key=lambda x: x[0])for i in range(1, len(intervals)):if intervals[i][0] < intervals[i - 1][1]:return Falsereturn True
Merging Intervals
When an interval overlaps with the previous interval in a list of intervals sorted by start times, they can be merged into a single interval.
To merge an interval into a previous interval, we set the end time of the previous interval to be the max of either end time.
prev_interval[1] = max(prev_interval[1], interval[1])
In Merge Intervals, we are given a list of intervals and need to return a list with all overlapping intervals merged together. We create a new list containing the merged intervals, sort the intervals by their start times, and then iterate over each interval. If the current interval overlaps with the last interval in the merged list, we merge the current interval into the last interval in the merged list. Otherwise, we add the current interval to the merged list.
def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged
Sorting by End Time
To see why we sometimes want to sort by end times instead of start time, let's consider the question of finding the maximum number of non-overlapping intervals in a given list of intervals.
Our solution will sort the intervals, and then greedily try to add each interval to the set of non-overlapping intervals.
If we sort by start time, we risk adding an interval that starts early but ends late, which will block us from adding other intervals until that interval ends.
For example, given the following intervals, if we sort by start time, choosing the first interval prevents us from adding another interval until after time 18. This blocks the remaining intervals from being added to the set of non-overlapping intervals, even though none of those intervals overlap with each other.
If instead we sort by end time, we can start by adding the intervals that end the earliest. Intuitively, this frees time for us to add more intervals as early as possible, and yields the correct answer.
Non-Overlapping Intervals
This is the basis for the question Non-Overlapping Intervals, in which we are given a list of intervals and asked to find the maximum number of non-overlapping intervals.
We sort the intervals by their end times, and then iterate over each interval, keeping a count of all intervals that overlap with the last interval in the non-overlapping set. We return the total number of intervals minus the count of overlapping intervals.
def nonOverlappingIntervals(intervals):if not intervals:return 0intervals.sort(key=lambda x: x[1])end = intervals[0][1]count = 1for i in range(1, len(intervals)):# Non-overlapping interval foundif intervals[i][0] >= end:end = intervals[i][1]count += 1return len(intervals) - count
Practice Problems
Working through these questions will give you more practice with intervals:
| Question | Difficulty |
|---|---|
| Can Attend Meetings | Easy |
| Insert Interval | Medium |
| Non-Overlapping Intervals | Medium |
| Merge Intervals | Medium |
| Employee Free Time | Hard |
Loading comments...