BS on Answer | Greedy | Easy Explanation | Optimal
IntuitionSince the problem involves minimizing the maximum, we apply BS on Answer here.Here, we are asked to minimize the capability which is defined to be the
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Since the problem involves `minimizing the maximum`, we apply BS on Answer here.

Here, we are asked to minimize the `capability` which is defined to be the maximum amount of money that the robber robs from the houses. We need to steal from atleast `k` houses and we cannot steal from two-adjacent houses.

So while applying the BS, we keep our constraint on having a particular `mid`, ie our maximum value (capacity), are we able to rob atleast `k` houses, if yes, we shift our `high` to left, else we increase our `low`. 

In order to count the number of houses we can rob, we apply `greedy approach` and traverse from left to right, and if the current `nums[i]` is `<= mid`, we can rob this house and we skip the next house.
(This approach works here because it allows us to have more numver of houses, and we are just concerned with the number of houses)
> Why This Greedy Choice is Valid
-Earliest Opportunity:
When you find a house that meets the candidate condition (its value is small enough), you take it immediately. This is like saying, "I’ll grab this available option now so I can still have as many choices as possible later."
If you skip a house that qualifies, you won't get any benefit later — you might only end up with houses having equal or higher amounts or lose the chance to rob enough houses.
-No Better Future Option:
Since houses are in a fixed order, if a house qualifies, picking it does not block any future opportunity because you only block the very next house. You are maximizing the number of houses you can pick under the candidate threshold.

To sum up, why greedy works:
- Greedy decision: Always take a house if it meets the candidate condition because it increases your count without harming future selections (except for the next immediate house which you must skip).

- No risk in taking early: Since houses are fixed in order, picking the first possible option gives you the best chance to maximize the count.

- Feasibility check: You don't need to consider every combination—just a simple left-to-right scan will tell you if the candidate capability works.

Eg: nums[] = [2, 7, 6, 1, 3] and let's say mid = 7
Then if we follow greedy approach, we can select: 2, 6, 3 (count = 3)
But if we don't follow greedy approach and not select 2, then final selection would look: 7,1 (count  = 2)
So this hints us to use a greedy approach as it will help us to increase the count of houses which we are concerned.

# Approach
<!-- Describe your approach to solving the problem. -->
To implement this, we take `low = 1` as this value is the smallest possible value of `nums[i]` (as per given constraints) and `high = *max_element of the array` as the robber cannot rob more than this.

Then for each value of `mid`, we check the count of houses we can rob (by applying the greedy approach), if it is `>= k`, we can shift our `high` to `mid - 1` and check for a smaller value that satisfies our condition.
Else we increase our `low` to have more count of houses.

# Complexity
- Time complexity: O(nlogk)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(1)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int canRob(vector<int>& nums, int& maxi){
        int n = nums.size();
        int cnt = 0;
        for(int i=0; i<n; i++){
            if(nums[i]<=maxi){
                cnt++; i++;
            }
        }
        return cnt;
    }

    int minCapability(vector<int>& nums, int k) {
        int n = nums.size();
        int low = 1, high = *max_element(nums.begin(), nums.end());
        while(low<=high){
            int mid = (low+high)/2;
            if(canRob(nums,mid)>=k) high = mid - 1;
            else low = mid + 1;
        }   

        return low;
    }
};
```
['Array', 'Binary Search', 'Greedy', 'C++']