# Greedy

## 经典题目

[*11 Container With Most Water*](https://leetcode.com/problems/container-with-most-water/description/)

Maintain a global res. Start from the two ends and move towards the middle using two pointers. Every time we try to increase the height: we pick the lower side, and move that index to the next element, so as to ensure we have the maximum area of current width.

```java
public int maxArea(int[] height) {
    if (height == null || height.length == 0) return 0;
    int res = 0;
    int i = 0, j = height.length - 1;
    while(i < j) {
        int cur = (j - i) * Math.min(height[i], height[j]);
        res = Math.max(res, cur);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}
```

[*134 Gas Station*](https://leetcode.com/problems/gas-station/description/)

Based on two facts:

1. if start from A we cannot reach B, then any gas station in the between cannot reach B. (B is the first one cannot reach)&#x20;
2. if total gas >= total cost, there must be a solution

```java
public int canCompleteCircuit(int[] gas, int[] cost) {
    int start = 0;
    int tank = 0;
    int total = 0;
    for (int i = 0; i < gas.length; i++) {
        if (tank + gas[i] - cost[i] < 0) {
            start = i + 1;
            tank = 0;
        } else {
            tank += gas[i] - cost[i];
        }
        total += gas[i] - cost[i];
    }
    return total >= 0 ? start : -1;
}
```

[*621. Task Scheduler*](https://leetcode.com/problems/task-scheduler/description/)

It's easier to get the number of empty slots first.

```java
/*
    A * * * *
    A * * * *
    A * * * *
    A
    
    total number of empty slots = (map['A'] - 1) * n
*/
public int leastInterval(char[] tasks, int n) {
    int[] map = new int[26];
    for (char c : tasks) {
        map[c - 'A']++;
    }
    Arrays.sort(map);
    int max = map[25] - 1;
    int emptySlots = n * max;
    for (int i = 24; i >= 0 && map[i] > 0; i--) {
        emptySlots -= Math.min(map[i], max);
    }
    return emptySlots > 0 ? emptySlots + tasks.length : tasks.length;
}
```

[*885 Boats to Save People*](https://leetcode.com/contest/weekly-contest-96/problems/boats-to-save-people/)

```java
/*
	Method 1: Greedy.
	Always pick one big number and one small number, and determine whether the sum is larger than limit or not.
		
	First of all, sort the array in increasing order.
	Then, use two pointers to search from two sides of the array, and check the relation between the sum and limit.
	If sum <= limit, meaning these two persons could share a same boat. So, we move on to the next couple.
	If sum > limit, we try to send larger person first, because that way, we are more likely to let two persons in the remaining share the same boat.
*/
	
public int numRescueBoats(int[] people, int limit) {        
    Arrays.sort(people);
    int left = 0, right = people.length - 1;
    int ans = 0;
    while (left < right) {
        if (people[right] + people[left] > limit) {
            ans += 1;
            right--;
        } else {
            ans += 1;
            right--;
            left++;
        }
    }
    return left == right ? ans + 1 : ans;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/greedy.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.