The busiest band
- O(n log n) · Hard
- Full plan
- Python
- JavaScript
- sorting
- lists
- indexes
Problem
The antenna at Kepler Base can only listen to one band at a time, and the band has a fixed width. You want to point it where the most ships are. Write a function that takes frequencies, a list of positive integers (one per ship; it may be empty and may have repeats), and width, an integer from 0 up. Return an integer: the most ships that fit together in one band, that is, in a group where the highest frequency minus the lowest is width or less. Repeats each count, and the edge is in: a difference equal to width does fit.
With 101, 98, 105, 99, 120, 104 and 103 and width 5, the band from 99 to 104 catches 99, 101, 103 and 104: that is 4, and no band catches 5.
With a single ship the answer is 1; with no ships, 0.
Examples
The example
[101, 98, 105, 99, 120, 104, 103], 5 → 4
The edge is in
[10, 13, 16], 3 → 2
Repeats with width 0
[50, 50, 50, 52], 0 → 3
The best band is at the end
[88, 90, 91, 95, 96, 97, 98], 4 → 4
A single ship
[7], 0 → 1
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def band(frequencies, width):
passJavaScript
function band(frequencies, width) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.
More O(n log n) challenges
- The cars that stay putPython · JavaScript · lists · sorting · division
- The cheapest billPython · JavaScript · sorting · lists · indexes
- The flipping spellsPython · JavaScript · sorting · lists · conditionals
- The galleon's holdPython · JavaScript · strings · sorting · loops
- The game shopPython · JavaScript · sorting · loops · comparisons
- The height of the sawPython · JavaScript · lists · search · comparisons