• 奇怪的做法：28ms
• 正常的合并：24ms

## 题意

AB两个闭区间数组，它们分别都是排过序的，且每个数组里的区间之间互不相交。请求出两个数组中闭区间的交。

• 排序：124ms
• 双指针：104ms

## 题意

• face up：如果你的power >= token[i]，则可以令power -= token[i]，且points++
• face down：如果你的points > 0，则可以令power += token[i]，且points--

## 分析

$$(points_A, power_A) > (points_B, power_B) \iff \begin{cases} points_A > points_B \\ points_A = points_B, \quad power_A > power_B \end{cases}$$

（就是规定了一个std::pair出来……）

• 计数：8ms
• 2Sum：4ms

## 分析

• 没有判断k是否在[0, 100]范围内，所以RE了
• 忘记A[i]的下限是0了，所以WA了
• 数量计算的时候爆int了，所以又WA了

……

• 根据0 <= A[i] <= 100进行去重
• 根据2Sum或者3Sum的思路进行指针优化

• 额外空间：96ms
• 双指针：68ms

• 双指针：0ms
• 栈：4ms

（非常简洁的写法）

• 分块扫描：148ms
• 滑动窗口：192ms

• 平凡的遍历：44ms
• 平凡的排序：36ms
• 不平凡的双指针：28ms

## 分析

### 一种证明贪心算法正确的方法

S表示一种最优解（显然，由于优化目标只是船的数量，最优解可能不止有一种），O表示我们的算法输出的解。

1. 贪心选择性质（greedy choice property）：选择只需依赖于当前情形，不需要依赖于未来的选择和子问题的其他解。

(a) 如果hi不能和其他任何人进入同一艘船，则在SO中，hi都独自处于一艘船中。显然，在这种情况下，我们的这一选择是最优的，贪心选择性质维持不变。

(b) 如果hi可以和其他某一个人进入一艘船，则在O中，根据我们的算法，hi和最轻的人lo必然位于同一条船上。

S中，如果他们也在同一条船上，则我们的这一步骤是最优的，贪心选择性质保持不变；如果他们不在同一条船上，则我们可以把hilo在船上的同伴m交换一下。显然，m <= hi，因此交换是可以进行的。因为交换没有导致船变多，我们得到了一个新的最优解T，且在这种解中，hilo在同一条船上。这表明，我们的第一个步骤——把hilo放进同一条船中——是一个最优步骤，贪心选择性质也维持不变。

1. 最优子结构性质（optimal substructure property）：对原问题的最优解必然包含对子问题的最优解

P表示规模为n的原问题，其中n = people.length。从上述推导中，可以看出，在第一步之后，我们得到了一个子问题P'，规模为n'（如果hi独自占据一艘船，则n' = n - 1，否则n' = n - 2）。我们可以相似地对P'中的hi'lo'进行和刚才一样的操作。

### 对于上述贪心算法的另一种理解

• 每个人只能在自己对应的区间中选点
• 点不能重复选择

### 在Leetcode上的英文回答

https://leetcode.com/problems/boats-to-save-people/discuss/156748/Python-short-2-pointer-solution-and-some-thoughts/166286

In short: I think both "smallest" and "possibly maximum" methods are correct, and they are in some way equivalent.

Another person has provided a formal proof for the "smallest" selection method. (6 lines Java O(nlogn) code, sorting + greedy, with greedy algorithm proof. ) Of course, that method is correct, but this might not be immediately obvious. So I'd like to share my understanding of this problem with you. (So it's not a formal proof.)

Let mid = floor(limit/2), and divide those people into two groups: 'heavy' people, whose weight > mid; and 'light' people, whose weight <= mid. Minimizing the number of boats is equivalent to maximizing the number of boats with two people in them. It is obvious that, if a 'heavy' person wants to sit in a boat with another person, the other person must be a 'light' one; on the other hand, a 'light' person can certainly sit with another 'light' person, and maybe some of the 'heavy' people.

Now, a solution is at hand: we first try to pair each 'heavy' person with a 'light' person, and put them in a boat; when a 'heavy' person can't find a pair, we put him alone in a boat; finally, if there are any 'light' person left, we can arbitrarily pair them together. The biggest question is, how can we maximize these 'heavy'-'light' pairs?

Sort all the people in ascending order. Let n = people.length, and suppose there are altogether m heavy people, denoted by people[n-m], people[n-m+1], ... people[n-1]. After sorting, the 'light' people that a 'heavy' person can pair with will form a interval. Denote these intervals by [0, r_{n-m}), [0, r_{n-m+1}), ..., [0, r_{n-1}). (Intervals might be empty)

Example: limit = 8, people = [2, 3, 3, 5, 6, 7]

In this example, heavy = [5, 6, 7], light =[2, 3, 3].

• For 7, the interval is [0, 0) (no one can sit with 7);
• For 6, the interval is [0, 1) (2 can sit with 6);
• For 5, the interval is [0, 3) ([2, 3, 3] can all sit with 5).

And it is obvious that r_{n-m} >= r_{n-m+1} >= ... >= r_{n-1} >= 0. So these intervals are all overlapping, and the left endpoints are all zero.

Now we can analyze the difference between "smallest" and "possibly maximum" methods. When we choose the "smallest" person, we are choosing the leftmost point of the interval (which hasn't be chosen yet); when we choose the "possibly maximum" person, we are choosing the rightmost point of the interval (which hasn't be chosen yet).

Because all intervals has 0 as the left endpoint, when we start from the heaviest person, only when r_k < k (k is the number of 'heavy' people we have considered or is considering) can this 'heavy' person not find a 'light' person to pair. So, in these two methods, we find different 'light' people for the 'heavy' people to pair, but the set of 'heavy' people who cannot find a pair is the same.

Example: limit = 8, people = [1, 2, 2, 2, 3, 4, 5, 6, 7, 7]

people[i] k interval "smallest" pair "possibly maximum" pair
people[9] = 7 1 [0, 1) 1 1
people[8] = 7 2 [0, 1) - -
people[7] = 6 3 [0, 4) 2 2
people[6] = 5 4 [0, 5)` 2 3

• 非原地版本：98.65%
• 原地版本：98.65%