0
$\begingroup$

N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?

N is an array containing location of each house. K is an integer value.

I am unable to identify the algo for this. I tried solving by taking location of 1st and last house, then dividing by K, this will give me max range of each streetlight. However, assume N=[3,4,5,10,13] and K=3. With division this wont work.

$\endgroup$

1 Answer 1

1
$\begingroup$

This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius

Key Idea: Binary search for the diameter, then use that to find the radius.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.