Intervals

Sort first, always

Almost every interval problem starts by sorting intervals by start time (or end time for scheduling). Once sorted, overlaps and gaps become adjacent comparisons instead of an all-pairs search.

Merge overlapping intervals

After sorting by start, walk through and merge whenever the current interval's start is <= the last merged interval's end.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            merged[-1][1] = max(last_end, end)
        else:
            merged.append([start, end])
    return merged

Output:

merge([[1,3],[2,6],[8,10],[15,18]])
# [[1,6],[8,10],[15,18]]

Interval scheduling (max non-overlapping)

To fit the most non-overlapping intervals, sort by end time and greedily keep an interval whenever it starts after the last kept interval's end.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float('-inf')
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

Output:

max_non_overlapping([[1,2],[2,3],[3,4],[1,3]])  # 3

Common variants

Insert a new interval into a sorted list, find minimum meeting rooms needed (use a heap of end times), and check if a person can attend all meetings — all built on the same sort-then-scan idea.