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

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

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

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

设那些个区间在 $R$ 中，单点在 $L$ 中。方便起见，我们 $i$ 表示左部的 $i$ 号点，用 $[U, V] \subset [l_i, r_i]$ 这样的区间表示一个 $i$ 出边集合的子集。而对于右部点，我们也直接用某个数字 $v$ 表示，这和左部点记号有重合，下面的论证读者要自行分辨哪个数字是左部点，哪个是右部点。

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

在第 $i$ 步循环中：

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

我们归纳证明这一循环不变式：在第 $i$ 步循环结束后，$S$ 覆盖了 $\displaystyle \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$ 当时找到了 left most 的点，而且到外层第 $i$ 步也没被换下来，则这个是显然成立的。

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

  • 如果 $k$ 当时找到了 left most 的点，而且在外层第 $i$ 步之前被换下来。

    假设是在外层第 $i' < i$ 步被换下来，则在外层归纳的第 $i'$ 步中已经保证 $[l_k, r_k]$ 被覆盖。

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

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

  • 如果 $k$ 当时没有找到 left most 的点，则外层第 $k$ 步的时候已经把 $[l_k,r_k]$ 对应的匹配邻居换下来了，这时候 $[l_k, r_k]$ 是被覆盖的。

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

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

  • 如果 $k$ 当时找到了 left most 的点，而且其就是在外层第 $i$ 步被换下来的，于是 $p_k\in [l_i,r_i]$，我们考虑 $[l_k,r_k]$ 这里面的边：

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

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

      • 如果 $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$ 的时候，$\displaystyle \bigcup_{j=1}^{k-1} [l_j,r_j]$ 都被覆盖了，和算法执行前 $k-1$ 步的效果是一样的，所以可以说「被之前的点覆盖」。

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

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

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

外层归纳完成。$\Box$