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.