fork download
copy 
  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String[] args) {
  4.         int[] chairs = {1, 2, 4, 8, 9};
  5.         int c = 3;
  6.         int result = largestMinDistance(chairs, c);
  7.         System.out.println(result); // Output: 3
  8.     }
  9.  
  10.     public static int largestMinDistance(int[] chairs, int c) {
  11.         int n = chairs.length;
  12.         Arrays.sort(chairs);
  13.         int left = 0, right = chairs[n - 1] - chairs[0];
  14.         int result = 0;
  15.  
  16.         while (left <= right) {
  17.             int mid = left + (right - left) / 2;
  18.             if (isValid(chairs, c, mid)) {
  19.                 result = mid;
  20.                 left = mid + 1;
  21.             } else {
  22.                 right = mid - 1;
  23.             }
  24.         }
  25.  
  26.         return result;
  27.     }
  28.  
  29.     public static boolean isValid(int[] chairs, int c, int minDistance) {
  30.         int count = 1;
  31.         int lastPosition = chairs[0];
  32.  
  33.         for (int i = 1; i < chairs.length; i++) {
  34.             if (chairs[i] - lastPosition >= minDistance) {
  35.                 count++;
  36.                 lastPosition = chairs[i];
  37.             }
  38.         }
  39.  
  40.         return count >= c;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0.07s 52648KB
comments (?)
stdin
copy 
1
5 3
1 2 4 8 9
stdout
copy 
3
https://ideone.com/y7yjHG
language:
Java (HotSpot 12)
created:
9 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!