Java || Binary Search + Greedy with Explanation
Intuition\nBinary Search is always a good option to try if you met the Minimum maximum question (or Maximum minimum question).\n\nThere are 2 thoughts for this 
# Intuition\n`Binary Search` is always a good option to try if you met the Minimum maximum question (or Maximum minimum question).\n\nThere are 2 thoughts for this question.\n\n1. If the minimum feasible capability is `i`, then all capabilities larger than `i` are also possible. That fits the nature of `binary search`.\n\nSo the current problem becomes how we can verify if the current capability is possible? \n\n2. we can just use `Greedy` to find out if the current capability is feasible or not. We always choose the left feasible house first because it can\'t be worse than selecting the right one. \n\nWe can use `Contradiction` to prove that. \nFor example, there are two adjacent feasible houses. If the solution is we choose the right house and other houses on its right, then it is always feasible that we choose the left house instead of the right one. Because if the other houses are not adjacent to the right house, then they can\'t be adjacent to the left house as well.\n\n# Code\n```\nclass Solution {\n    public int minCapability(int[] nums, int k) {\n        // find the range of the possible capabilities\n        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;\n        for (int num : nums) {\n            max = Math.max(max, num);\n            min = Math.min(min, num);\n        }\n        // binary search\n        int start = min, end = max;\n        while (start < end) {\n            int mid = start + (end - start) / 2;\n            if (isPossible(nums, mid, k)) {\n                end = mid;\n            } else {\n                start = mid + 1;\n            }\n        }\n        return start;\n    }\n    private boolean isPossible(int[] nums, int target, int k) {\n        // greedy here\n        int lastStolenIndex = -2;\n        for (int i = 0; i < nums.length; ++i) {\n            if (nums[i] <= target && lastStolenIndex + 1 < i) {\n                k -= 1;\n                lastStolenIndex = i;\n                if (k == 0) return true;\n            }\n        }\n        return false;\n    }\n}\n```
['Binary Search', 'Greedy', 'Java']