Interval Problems

For most interval questions, you have two main approaches:

1. Sort intervals by start time
2. Sort intervals by end time

Sort Intervals by Start Time

This approach is useful for checking if intervals overlap and for merging overlapping intervals.

# Check if person can attend all their meetings.
intervals.sort(key=lambda x: x[0])
for i in range(len(intervals)-1):
    cur, nxt = intervals[i], intervals[i+1]
    if cur[1] > nxt[0]:
        return False
return True 

When you find overlapping intervals, you can merge them by updating the end time:

Merging intervals: take previous interval, set prev.end = max(prev.end, current.end)

Sort Intervals by End Time

This approach is useful for picking as many non-overlapping intervals as possible (activity selection problem).

The optimal solution is to greedily select intervals with the earliest end times: \(maxMeetings(start, end, meetings) = 1 + maxMeetings(start+meetings[0][1], end, meetings[1:])\)

It’s even easier iteratively:

def maxNonOverlap(intervals):
    intervals.sort(key=lambda x: x[1])  # Sort by end time
    count = 0
    end = float('-inf')
    
    for start, finish in intervals:
        if start >= end:  # No overlap with last selected interval
            count += 1
            end = finish
    
    return count

Fun fact: “Finding the minimum number of intervals to remove for non-overlapping intervals” is equivalent to “Finding the maximum number of non-overlapping intervals you can take” - just subtract your answer from the total number of intervals.

Summary

In short, there are two archetypal questions in interval problems:

1. Merging overlapping intervals - sort by start time
2. Maximum number of non-overlapping intervals - sort by end time

Most interval problems are modifications or inversions of these two types!