「区间二分图」贪心匹配的正确性

U 群里一位群友（其实他是我学长）提出的问题，我觉得很有趣的，记录下来。证明的记号用的比较「口语化」。

上图该出了一个算法，我们要证明这一算法确实给出了图中所示二分图的一个最大匹配。

Proof：我们用该算法构造一个大小相同的点覆盖，再由 König 定理即可证明最优性。

设那些个区间在 $R$ 中，单点在 $L$ 中。为了fangbianqijian

维护一个集合 $S$，初始时 $S=\varnothing$。

在第 $i$ 步循环中：

• 如果 $i$ 点可以找到对应的 left most 的顶点，记为 $p_i$，则令 $S\gets S\cup \{i\}$。
• 如果不行，则对 $[l_i,r_i]$ 这一个区间里的每个点 $v$，在 $L$ 中找到点 $u$，使得 $p_u=v$。然后 $S\gets S-u+v$（对每个 $v$ 都弄一次，如果这个 $u$ 之前就变成 $v$ 了，则不需要做这个操作，不妨把这个操作成为「把 $u$ 换下来」）。

我们证明这一循环不变式：在第 $i$ 步循环结束后，$S$ 覆盖了 $\bigcup_{k=1}^i [l_k,r_k]$ 这些个边。

• 第一个 case 显然。

• 第二个 case：显然 $[l_i,r_i]$ 被覆盖了（因为里面的每个点都被加上去了）。而对于 $i$ 之前的 $k$，我们再用一次归纳法：在 $[l_i,r_i]$ 这些个点全部被换上来后，还是有： $\forall 1\le k\le i-1$$，[l_k,r_k]$ 是被覆盖的：

  • 如果 $k$ 之前就在上面，而且也没被换下来，则这个是显然成立的。

    注意这一部分是不需要归纳奠基的。

  • 如果 $k$ 之前就被换下来了，则在这之前 $[l_k,r_k]$ 就被填满了。

    而「换下来」的操作只会增加 $S$ 中属于 $R$ 的点，所以 $[l_k,r_k]$ 仍然是被填满的。

    注意这一部分也是不需要归纳奠基的。

  • 如果 $k$ 就是在这一步被换下来的，于是 $p_k\in [l_i,r_i]$，我们考虑 $[l_k,r_k]$ 这里面的边：

    • 在 $[l_k, l_i)$ 这之间的边肯定被之前的点覆盖（不然 $k$ 不会选择 $p_k$）。

      「被之前的点覆盖」这里的推理如下：

      • 如果 $k=1$，则 $p_k=l_k$。又因为 $r_k\le r_i$，所以 $[l_k,r_k]\subset [l_i,r_i]$，把 $[l_i,r_i]$ 覆盖了也就把 $[l_k,r_k]$ 覆盖了。

      • 如果 $k>1$，则这里用一下归纳奠基。归纳到 $k$ 的时候，$\bigcup_{j=1}^{k-1} [l_j,r_j]$ 都被覆盖了，和算法执行前 $k-1$ 步的效果是一样的，所以可以说「被之前的点覆盖」。

    • 在 $[l_i,r_i]$ 中的边自然被覆盖。

    • 而因为 $r_k\le r_i$，所以没有更右边的边了。

    综上这些个边全部被覆盖了。

归纳完成。$\Box$