当我们考虑一个信息问题,特别是一个贪心问题的时候,其实就是通过题设的少量条件来寻找规律从而破题。
比如下面这道题,就是通过分析已知数据的可能组合来寻找正确解法。
区间调度问题
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是对称的,所以上述思路反过来也是对的,只是没有原先那么自然。