⬅ Previous Topic
Painter's Partition ProblemNext Topic ⮕
Median of Two Sorted Arrays of Different Sizes⬅ Previous Topic
Painter's Partition ProblemNext Topic ⮕
Median of Two Sorted Arrays of Different SizesTopic Contents
You are given a sorted array of integers representing the positions of existing gas stations along a road. You are also given an integer k
, which represents the number of additional gas stations you are allowed to add anywhere between the existing ones.
Your task is to minimize the maximum distance between any two adjacent gas stations after placing the k
new stations optimally.
Return the smallest possible maximum distance between gas stations after the optimal placement, rounded to 6 decimal places if required.
low = 0
and high = max(arr[i+1] - arr[i])
.high - low > 1e-6
:mid = (low + high) / 2
.k
stations so that max distance ≤ mid
.high = mid
.low = mid
.high
(smallest valid max distance).def is_possible(arr, k, dist):
count = 0
for i in range(len(arr) - 1):
gap = arr[i+1] - arr[i]
count += int(gap // dist) # Number of stations needed in this gap
return count <= k
def minimize_max_distance(arr, k):
low = 0.0
high = max(arr[i+1] - arr[i] for i in range(len(arr)-1))
eps = 1e-6
while high - low > eps:
mid = (low + high) / 2
if is_possible(arr, k, mid):
high = mid # Try to minimize max distance further
else:
low = mid
return round(high, 6)
# Example
arr = [1, 2, 8]
k = 1
print("Minimum Max Distance:", minimize_max_distance(arr, k))
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n × log(max_gap/eps)) | We perform binary search over precision range and for each guess, count stations in O(n). |
Average Case | O(n × log(max_gap/eps)) | Each step of binary search tests feasibility by iterating through the array. |
Worst Case | O(n × log(max_gap/eps)) | In the worst case, we perform many precision steps, each involving scanning the entire array. |
O(1)
Explanation: No extra space is used apart from a few variables for binary search and counters.
⬅ Previous Topic
Painter's Partition ProblemNext Topic ⮕
Median of Two Sorted Arrays of Different SizesYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.