Intervals

How it works

Interval problems become easy the moment the intervals are sorted. Sorted by start, overlapping intervals sit next to each other, so a single pass can merge them, count gaps, or insert a new one. Without sorting, every interval must be compared with every other.

Two intervals [a, b] and [c, d] overlap exactly when a <= d and c <= b (or with strict inequalities if touching endpoints do not count). Decide the touching rule up front; it is the most common source of wrong answers.

For 'remove the fewest intervals to make the rest disjoint' or 'schedule the most meetings', sort by end time instead. Taking the interval that finishes first leaves the most room for everything after it.

For 'how many overlap at once' (meeting rooms, maximum concurrent events), sweep over sorted events: +1 at each start and -1 at each end, or keep a min-heap of end times. The peak of the running count is the answer.

How to attack it

1. 1Fix the overlap rule, including whether touching endpoints overlap.
2. 2Sort by start for merging and inserting, by end for selecting the most disjoint.
3. 3Keep a 'current' interval and extend or close it in one pass.
4. 4Use a sweep or a heap of end times for maximum concurrency.
5. 5Check empty input and a single interval.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

import heapq


def merge(intervals):
    intervals.sort(key=lambda iv: iv[0])     # sort by start
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:  # overlaps the last one
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged


def max_disjoint(intervals):
    intervals.sort(key=lambda iv: iv[1])     # sort by end
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:                # fits after the last chosen
            count += 1
            last_end = end
    return count


def rooms_needed(intervals):
    intervals.sort(key=lambda iv: iv[0])
    ends = []                                # min-heap of end times in use
    for start, end in intervals:
        if ends and ends[0] <= start:
            heapq.heappop(ends)              # reuse the room that freed up
        heapq.heappush(ends, end)
    return len(ends)

What it costs