Vectors, pairs and sorting

A vector is a resizable array, the container you will use in almost every problem. A pair holds two values, and pairs compare by the first value and then by the second, so sorting a vector of pairs sorts by one key and keeps a second value, such as the original index, alongside it.

sort runs in O(n log n) and accepts a comparator, a small function (often a lambda, an unnamed inline function) that says which of two elements comes first. Custom orders drive many greedy solutions, so get comfortable writing them.