7.2 贪心【基础】

当我们考虑一个信息问题,特别是一个贪心问题的时候,其实就是通过题设的少量条件来寻找规律从而破题。

比如下面这道题,就是通过分析已知数据的可能组合来寻找正确解法。

区间调度问题

Problem
有n项工作,每项工作分别在si开始,ti结束。对每项工作,你都可以选择参加或不参加,但选择了参加某项工作就必须至始至终参加全程参与,即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。

Input Data
第1行,一个整数n,表示有n项工作;
第2行,n个整数,表示第1到n项工作的开始时间;
第3行,n个整数,表示第1到n项工作的结束时间。

Output Data
共1行,一个整数,表示最多能参与多少项工作。

本题有用的内容其实只有si和ti,注意到本题不属于一般性题目,因此解法必然与这两个数据有直接联系。

考虑第一种可能性:与si有关。

容易想到将所有区间以左端点为第一关键字,长度为第二关键字进行排序,然后贪心地选择。

然而这个思路存在反例,比如:

3
1 2 4
1000000 3 5

考虑第二种情况:与ti有关。

这个时候我们以右端点为关键字进行排序,然后从右端点最小的开始从左往右记录。

这个正确性可以通过反证法来证明:

假设该解法不具有正确性,那么必然存在反例,使该解法不能取到最大的答案。

考虑最朴素的情况:即全局内只有三段时间(保证不能都取)。那么运用此解法应当得出1,而正解应为2。

接下来考虑这三段时间的构造:不妨设其为\(a,b,c\),且此解法得出只能选\(a\)。

由于不能选\(b,c\),所以这二者都与\(a\)存在交集。

显然此时\(b,c\)也存在交集,推出矛盾,所以结论具有正确性。

考虑三段时间即可说明的正确性是显然的。

备注:事实上,由于si与ti是对称的,所以上述思路反过来也是对的,只是没有原先那么自然。

上一篇:洛谷P1091 合唱队形


下一篇:TM4C123G入门(一)