Loading
Loading
A rail line has mounting posts at fixed distances from the depot. Engineers must clip vibration sensors onto some of the posts, at most one per post. Sensors placed close together pick up each other's noise, so the team wants them as far apart as possible.
Given the post positions in posts (not sorted) and the number of sensors, return the largest possible value of the smallest distance between any two placed sensors.
posts = [1, 2, 8, 4, 9], sensors = 3sorted: 1 2 4 8 9the check is easiest on sorted positionsgap 4?1, then 8 — only two sensors fitgap 3?1, 4, 8 — three sensors fitanswer 33 works and 4 does not3Sign in to keep a note here. It is free, and nobody else can see it.
Sign inExample 1
Sign in to open hints.
Struggling is where the learning happens. Open this once you have genuinely tried, or once the hints have run out.
O(n log n) time · O(n) space
Input. Run your code to watch it work on this input, one line at a time.
Running code is turned off on this deployment. You can still read the problem, write code, use hints and the visualizer.
Tab moves focus out of the editor. Press Ctrl+M to let Tab indent instead.
No results yet
Run your code against the sample tests, or submit to run the full suite.
Posts at 1, 4 and 8 (or 1, 4, 9) keep every pair at least 3 apart; no choice reaches 4.
Example 2
With two posts and two sensors, the gap is the full distance.