Place Chargers in Baskets to Maximize the Minimum Distance Between Them
Solve this Problembaskets, the locations of every basket (given in no particular order), and an integer m, choose m of those baskets to place a charger in so that the smallest distance between any two chargers is as large as possible. Return that largest possible minimum distance.
Since the baskets aren't given sorted, the first step is sorting them — the greedy feasibility check (always jump to the next basket at least d away from the last placed charger) only makes sense once positions are in order. From there this becomes exactly the same pattern as maximizing the minimum spacing between placed sensors: if m chargers can all be placed at least d apart, that same greedy placement trivially works for any smaller d too. That "easier for a smaller distance" relationship is exactly what a binary search on the answerBinary Search on the AnswerThe search runs directly over the space of candidate answers rather than over the array's values. It applies whenever "is this candidate good enough?" is monotonic in one direction — here, achievability only ever improves as the candidate distance shrinks. needs — search the candidate distances directly, keeping the largest one that still manages to place every charger.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
2 ≤ number of baskets ≤ 10⁵ - ◆
0 ≤ baskets[i] ≤ 10⁹ (given in any order) - ◆
2 ≤ m ≤ number of baskets
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Distance From 1 Upward
BruteSort the basket positions first — the input isn't given in order. For a candidate minimum distance d, greedily place the first charger at the leftmost basket, then keep placing the next charger at the first basket at least d away from the last one placed. Try d = 1, 2, 3, ... and keep the largest d that still manages to place all m chargers; the moment a d fails, every larger d fails too. Correct, but re-scanning every basket for every single candidate distance wastes a lot of work.
O(n log n + n · maxDist)O(n)1class Solution {
2 public int maxMinDistance(int[] baskets, int m) {
3 int[] pos = baskets.clone();
4 Arrays.sort(pos);
5 int maxDist = pos[pos.length - 1] - pos[0];
6 int ans = 0;
7 for (int d = 1; d <= maxDist; d++) {
8 if (canPlace(pos, m, d)) {
9 ans = d;
10 } else {
11 break;
12 }
13 }
14 return ans;
15 }
16
17 private boolean canPlace(int[] pos, int m, int d) {
18 int count = 1, last = pos[0];
19 for (int i = 1; i < pos.length; i++) {
20 if (pos[i] - last >= d) { count++; last = pos[i]; }
21 }
22 return count >= m;
23 }
24}Optimal — Binary Search on the Distance
OptimalAfter sorting, whether a distance d is achievable is monotonic: the greedy placement that works for d also trivially works for any smaller distance, and fails the same way in reverse. That monotonic structure is exactly what binary search needs: search the candidate distances between 1 and the full span of the baskets, and whenever a candidate distance is achievable, remember it and try a bigger distance; otherwise it's too ambitious, so search smaller.
O(n log n + n · log(maxDist))O(n)1class Solution {
2 public int maxMinDistance(int[] baskets, int m) {
3 int[] pos = baskets.clone();
4 Arrays.sort(pos);
5 int lo = 1, hi = pos[pos.length - 1] - pos[0];
6 int ans = 0;
7 while (lo <= hi) {
8 int mid = lo + (hi - lo) / 2;
9 if (canPlace(pos, m, mid)) {
10 ans = mid;
11 lo = mid + 1;
12 } else {
13 hi = mid - 1;
14 }
15 }
16 return ans;
17 }
18
19 private boolean canPlace(int[] pos, int m, int d) {
20 int count = 1, last = pos[0];
21 for (int i = 1; i < pos.length; i++) {
22 if (pos[i] - last >= d) { count++; last = pos[i]; }
23 }
24 return count >= m;
25 }
26}