fork download
copy 
  1. // Problem: EV Charging Station Placement
  2. // A highway authority wants to install k electric vehicle charging stations across n pre-approved locations along a highway. The locations are given as an array of integers representing their positions (in km) on the highway.
  3. // To avoid congestion, the authority wants to place the stations such that the minimum distance between any two stations is as large as possible.
  4. // Return that maximum possible minimum distance.
  5. // Example1 :
  6.  
  7. // locations = [1, 2, 4, 8, 9],  k = 3
  8. // Output: 3
  9.  
  10. // Explanation: Place stations at positions 1, 4, and 9.
  11. //              Gaps: (4-1)=3, (9-4)=5 → minimum gap is 3.
  12. //              No other placement of 3 stations gives a minimum gap > 3.
  13.  
  14. // Example2 :
  15. // Input: locations[] = [10, 1, 2, 7, 5], k = 3
  16. // Output: 4
  17.  
  18. // Explanation: Sort the locations → [1, 2, 5, 7, 10].
  19. //              Place stations at positions 1, 5, and 10.
  20. //              Gaps: (5-1)=4, (10-5)=5 → minimum gap is 4.
  21. //              No other placement of 3 stations yields a minimum gap greater than 4.
  22.  
  23. // 
  24.  
  25.  
  26.  
  27.  
  28. /* package whatever; // don't place package name! */
  29.  
  30. import java.util.*;
  31. import java.lang.*;
  32. import java.io.*;
  33.  
  34. /* Name of the class has to be "Main" only if the class is public. */
  35. class Ideone
  36. {
  37.  
  38. 	private static int maxDistance(int[] location, int k){
  39. 		Arrays.sort(location);
  40. 		int low = 0;
  41. 		int high = location[location.length-1];
  42. 		int answer = 0;
  43. 		while(low<=high){
  44. 			int mid = low + (high-low)/2;
  45. 			if(canPlace(location,k,mid)){
  46. 				answer = mid;
  47. 				low = mid+1;
  48. 			}else{
  49. 				high = mid-1;
  50. 			}
  51. 		}
  52. 		return answer;
  53. 	} 
  54.  
  55. 	private static boolean canPlace(int[] location, int k, int mid){
  56. 		int stationPlaced = 1;
  57. 		int lastPosition = location[0];
  58. 		for(int i = 1; i < location.length; i++){
  59. 			if(location[i]-lastPosition >= mid){
  60. 				stationPlaced++;
  61. 				lastPosition = location[i];
  62. 			}
  63. 			if(stationPlaced>=k){
  64. 				return true;
  65. 			}
  66. 		}
  67. 		return false;
  68. 	}
  69.  
  70. 	public static void main (String[] args) throws java.lang.Exception
  71. 	{
  72. 		//[1, 2, 4, 8, 9],  k = 3
  73. 		int[] location = new int[]{10,1,2,7,5};
  74. 		int k = 3; 
  75.  
  76. 		System.out.println(maxDistance(location,k));
  77. 	}
  78. }
Success #stdin #stdout 0.07s 54496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
https://ideone.com/KGDNo5
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!