Expand description
§Cafeteria
We speed things up by first merging ranges. This is possible in O(n log n) instead of O(n²)
complexity by first sorting the ranges in ascending order of their start.
Interestingly, part one is harder than part two. We could check every ID against every range,
however this is slow. It’s much faster instead to first sort IDs in ascending order,
then for each range use a binary search to count
the number of IDs that it contains. Rust even provides a handy built-in
binary_search method on slices.
Functions§
Type Aliases§
- Input 🔒