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
Tag: sorting
Sorting in C++: Five Algorithms, Stability, and What the Merge Step Buys You
Almost nobody implements a sorting algorithm at work. You call std::sort and move on. So the usual defence of learning them — “it builds fundamentals” — is doing a lot of unpaid labour in that sentence. Here is a better reason, and it is the one this post is built on. Three of the five algorithms below contain a reusable subroutine that shows up as LeetCode problems in its own right. Merge sort’s merge step is a problem. Quicksort’s partition step is four problems. And one character inside merge sort decides whether the algorithm is stable, which changes what you READ MORE