API tools faq
paste
Advertisement
Kali_prasad

min fatigue possible after adding k stops at anywhere in between

Kali_prasad
May 14th, 2025
620
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.76 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. A20250511b_UberOA
  3. #binary_search
  4.  
  5. given you a list of travel stops by uber drivers in an array and they are strictly increasing
  6.  
  7. the fatigue is called as difference between the stops
  8. we need to decrease the maximum fatigue through out their entiner journey
  9. we can place a stop at any point of time but only k times
  10.  
  11. find the minimum possible max fatigue that can be done after inducing k stops
  12. -----------------------------------------------------------------------------------------------------
  13.  
  14. important thing to be noted here is -
  15.  
  16. lets say you have stops at 2 and 8 ,so the fatigue is 6
  17.  
  18. if you can place one stop between them you can put at 3
  19. then it makes 2 3 8 as stops fatigue btw 2-3 is 1 and 3-8 is 5
  20. so max fatigue shrink down to 5 ,but we can do it better what if
  21. we put the stop at middle point this makes the distance on either side of stop
  22. as equidistant which hopefully reduces the overall max
  23.  
  24.  
  25. what's now
  26. ideally to reduce fatigue we can put many stops and shrink down the max fatigue to 1
  27. but we can use utmost k stops it might not be possible
  28. lazily we can leave fatigue as it is and put no stops ,but thats bad
  29.  
  30. this makes it as binary search problem
  31.  
  32. choose a desiredFatigue x
  33. check if it is possible
  34. if possible then try for less desiredFatigue less than x
  35. else settle in search of possible less desiredFatigue more than x
  36.  
  37. assume the currFatigue say 5 between one of the stops is y
  38. but we need it to be desiredFatigue say 3
  39. this will give us stopsNeeded
  40. ceil(5/3)-1 => 1 just one stop is enough
  41. this brings us to the formula
  42. ceil(currFatigue /desiredFatigue)-1
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50. -----------------------------------------------------------------------------------------------------
  51.  
  52. input - stops and allowedStops
  53. 2 5 10
  54. 3
  55.  
  56.  
  57. output -
  58. 2
  59.  
  60. */
  61.  
  62. import java.util.*;
  63.  
  64.  
  65.  
  66.  
  67.  
  68. @SuppressWarnings({"unused","unchecked"})
  69. public class A20250511b_UberOA  {
  70.  
  71.     static Scanner sc = new Scanner(System.in);
  72.  
  73.     private static int[] getArray() {
  74.         String[] sArr = sc.nextLine().split(" ");
  75.         int[] arr = Arrays.stream(sArr).mapToInt(Integer::parseInt).toArray();
  76.         return arr;
  77.     }
  78.  
  79.     private static char[] getCharArray() {
  80.         String[] sArr = sc.nextLine().split(" ");
  81.         char[] cArr = new char[sArr.length];
  82.         for (int i = 0; i < sArr.length; i++) {
  83.             cArr[i] = sArr[i].charAt(0); // Take the first character of each string
  84.         }
  85.         return cArr;
  86.     }
  87.  
  88.     private static int getMax(int[] arr) {
  89.         int currMax = Integer.MIN_VALUE;
  90.         for (int curr : arr) {
  91.             currMax = Math.max(currMax, curr);
  92.         }
  93.         return currMax;
  94.     }
  95.  
  96.     private static boolean checkIfPossible(int desiredFatigue,int[] stops,int availableStops){
  97.         int lenn = stops.length;
  98.         int totalRequireStops = 0;
  99.         // System.out.println("desiredFatigue is " + desiredFatigue);
  100.         for(int i = 0;i<lenn-1;i+=1){
  101.             int currFatigue = stops[i+1]-stops[i];
  102.             int currStops = 0;
  103.             if(currFatigue>desiredFatigue){
  104.                 //putting a double is importan other wise java already make your answer rounded down
  105.                 currStops += (int)Math.ceil((double)currFatigue/desiredFatigue)-1;
  106.             }
  107.             // System.out.println("currStops is " + currStops);
  108.             totalRequireStops += currStops;
  109.         }
  110.         return totalRequireStops <= availableStops;
  111.     }
  112.  
  113.     private static int checkminPossibleMaxFatigue(int left,int right,int[] stops,int availableStops){
  114.         int ans = right;
  115.         while(left<=right){
  116.             int mid = (right-left)/2 + left;
  117.            
  118.             // System.out.println("left is " + left);
  119.             // System.out.println("right is " + right);
  120.             // System.out.println("mid is " + mid);
  121.             if(checkIfPossible(mid,stops,availableStops)){
  122.                 right = mid-1;//become greedy and choose for more minimum fatigue
  123.                 ans = mid;
  124.             }else{
  125.                 left = mid + 1;
  126.             }
  127.             // System.out.println("ans is " + ans);
  128.  
  129.         }
  130.         return ans;
  131.  
  132.     }
  133.    
  134.     public static void main(String args[]) {
  135.         // prepare the inputs
  136.  
  137.  
  138.        int[] stops = getArray();
  139.        int lenn = stops.length;
  140.        int availableStops = getArray()[0];
  141.        int maxi = -(int)(1e9+7);
  142.        for(int i = 0;i<lenn-1;i+=1){
  143.         maxi = Math.max(maxi,stops[i+1]-stops[i]);
  144.        }
  145.     //    System.out.println("maxi is "+maxi);
  146.        int ans = checkminPossibleMaxFatigue(1,maxi,stops,availableStops);
  147.        System.out.println("ans is "+ans);
  148.  
  149.     }
  150. }
  151.  
  152. class Pair{
  153.     int row;
  154.     int col;
  155.     public Pair(int i,int j){
  156.         this.row = i;
  157.         this.col = j;
  158.        
  159.     }
  160. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!