Intervals

Interval problems are about ranges: meetings, bookings, shifts, ranges of numbers. Most of them get much easier once you sort, usually by start time, because then you only ever compare each interval with the one before it.

Merging overlapping intervals: sort by start. If the next interval starts before the last merged one ends, they overlap, so stretch the end. Otherwise start a new one.

def merge(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Note the max: [1, 10] and [2, 3] overlap, but the merged end stays 10. For [[1, 3], [2, 6], [8, 10], [10, 12]] you get [[1, 6], [8, 12]].

The other big pattern is a sweep: turn each interval into a +1 at its start and a −1 at its end, sort all the points, and walk through them keeping a running count. The highest count is how many overlap at once, which is the number of meeting rooms you need.

• Ask if intervals are open or closed, and whether touching counts as overlapping.
• Sort first, and say what you're sorting by.
• Test it with nested intervals, touching intervals and an empty list.

Inserting a new meeting

You have a sorted list of non-overlapping busy times, [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]]. Insert a new meeting, [4, 8], and merge where needed.

1. You could add it and re-sort, which is O(n log n). Since the list is already sorted, one pass is enough.
2. First, copy every interval that ends before the new one starts. [1, 2] ends at 2, before 4, so it's copied.
3. Next, merge every interval that overlaps the new one, which means it starts at or before the new one's end. [3, 5], [6, 7] and [8, 10] all start at or before 8.
4. While merging, the new interval grows to the smallest start and the biggest end: from [4, 8] to [3, 10].
5. Add [3, 10], then copy everything left, which is [12, 16].
6. The result is [[1, 2], [3, 10], [12, 16]] in O(n).
7. Ask whether touching counts. If [3, 5] and [5, 6] should stay separate, change the merge check from 'start at or before end' to 'start before end'.

Things interviewers tend to ask once you've brought this up.

How many meeting rooms do you need?

Sort by start and keep a min-heap of end times. If the earliest end is at or before the next start, reuse that room. The biggest the heap gets is the answer.

What's the fewest intervals to remove so none overlap?

Sort by end time and greedily keep each interval that starts after the last kept one ends. Everything you didn't keep is the answer.

How do you find free time across several people's calendars?

Put all busy intervals together, merge them, and the gaps between the merged intervals are when everyone's free.

What if bookings arrive one at a time and you need to reject overlaps?

Keep bookings sorted, binary search for where the new one would go, and check only its neighbors on each side.

• Forgetting to sort first.
• Setting the merged end to the new end instead of the max of both, which breaks nested intervals.
• Not asking whether touching intervals overlap.
• Comparing every pair, which is O(n²).
• Changing the input list while looping over it.

• Heaps and priority queuesAlways have the smallest or largest item ready.
• Binary searchCut the search in half, even when you're searching for an answer.
• Hash maps and sliding windowsSwap nested loops for a single pass.