Interval problems look like a family of tricks. They are one trick applied seven ways, and the trick fits in a sentence: sort by start time, and every question about overlap becomes a question about the element you just looked at. Without the sort, “do any two of these overlap?” is a pairwise check over n² pairs. With it, an interval can only overlap the ones immediately around it, so one linear walk answers the question. Three of the seven problems below need nothing more than that walk. The other four need one extra structure — a heap — and READ MORE