信息学奥赛一本通 1324：【例6.6】整数区间

ybt 1324：【例6.6】整数区间

要想证明贪心选择可以得到最优解，只需要证明最优解包含每一次的贪心选择。 使用数学归纳法：

每次选择右端最小的区间的右端数字，并删掉所有包含该数字的区间。 用数学语言说，现有区间： e 1 = [ l 1 , r 1 ] , e 2 = [ l 2 , r 2 ] , . . . , e n = [ l n , r n ] e_1=[l_1,r_1], e_2=[l_2,r_2],...,e_n=[l_n,r_n] e1​=[l1​,r1​],e2​=[l2​,r2​],...,en​=[ln​,rn​] 选择右端点r最小的区间 e m = [ l m , r m ] e_m=[l_m,r_m] em​=[lm​,rm​]，删掉所有满足 r m ∈ e x r_m\in e_x rm​∈ex​的区间 e x e_x ex​

贪心选择：每次选择右端最小的区间的右端点数字

记右端最小的区间为 e m = [ l m , r m ] e_m = [l_m,r_m] em​=[lm​,rm​]，证明存在最优解包含 r m r_m rm​ 使用反证法：假设所有最优解都不包含 r m r_m rm​ 对于某一最优解，根据题意：“对于每一个区间,都至少有一个整数属于该集合”，所以一定要在区间 e m e_m em​中选择一个数字。假设该最优解中选择了区间 e m e_m em​中的数字 x x x且 x ≠ r m x \neq r_m x​=rm​，包含x的区间有p个，组成的集合为： E x = { e x 1 , e x 2 , . . . , e x p } E_x = \{e_{x1},e_{x2},...,e_{xp}\} Ex​={ex1​,ex2​,...,exp​}，选择x后，这些区间都被删掉，不再被考虑。 现在考虑在该最优解中用 r m r_m rm​替换 x x x，包含 r m r_m rm​的区间有q个，组成集合为： E r = { e r 1 , e r 2 , . . . , e r q } E_r=\{e_{r1},e_{r2},...,e_{rq}\} Er​={er1​,er2​,...,erq​}，由于 e m e_m em​是右端最小的区间，所以 E x E_x Ex​中的所有区间的右端都大于等于 r m r_m rm​，也就是说 r m r_m rm​在 E x E_x Ex​的每个区间中，亦即 E x ⊆ E r E_x\subseteq E_r Ex​⊆Er​。选择 r m r_m rm​后， E r E_r Er​中的所有区间都被删除，包括了 E x E_x Ex​中的所有区间。该最优解中其他数字不变，仍然可以形成一组最优解。而这组最优解包含了 r m r_m rm​，与假设相悖。因而原命题得证。

证明方法与证明第1点相似，不再赘述。

将所有区间排序，排序规则为：右端小的排在前面；如果右端相同，那么左端小的排在前面。 按顺序遍历各个区间，选择当前区间的右端点并记录，选择的数字个数加1。 继续遍历，如果当前区间的左端点小于等于之前记录的右端点，那么略过这个区间。 如果当前区间左端点大于之前记录的右端点，那么选择当前区间的右端点并记录，选择的数字个数加1。 重复上述过程，直至遍历完所有区间。