贪心算法——区间调度问题 · 算法程序设计

贪心算法——区间调度问题 <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">问题主题：区间调度问题</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">问题描述：有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。限制条件：1<=n<=1000001<=si<=ti,=109</td></tr><tr><td width="882" valign="top" style="width:661.75pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">样例：输入n=5s={1,2,4,6,8}T={3,5,7,9,10}输出3(选择工作1, 3, 5)</td></tr></tbody></table> ### 解题分析：对这个问题，如果使用贪心算法的话，可能有以下几种考虑： (1)、每次选取开始时间最早的； (2)、每次选取结束时间最早的； (3)、每次选取用时最短的； (4)、在可选工作中，每次选取与最小可选工作有重叠的部分；对于上面的四种算法，只有算法(2)是正确的，其它的三种都可以找到相应的反例。具体证明如下：数轴上有n个区间，选出最多的区间，使得这些区间不互相重叠。 **算法：** 将所有区间按右端点坐标从小到大排序，顺序处理每个区间。如果它与当前已选的所有区间都没有重叠，则选择该区间，否则不选。 **证明：** 显然，该算法最后选出的区间不互相重叠，下面证明所选出区间的数量是最多的。设fi为该算法所接受的第i个区间的右端点坐标，gi为某最优解中的第i个区间的右端点坐标。 **命题1.1** 当**i>=1**时，该算法所接受的第**i**个区间的右端点坐标**f**i**<=**某最优解中的第**i**个区间的右端点坐标**gi**。**** 该命题可以运用数学归纳法来证明。对于i=1，命题显然为真，因为算法第一个选择的区间拥有最小右端点坐标。令i>1，假定论断对i-1为真，即fi-1<=gi-1。则最优解的第i个可选区间所组成的集合包含于执行该算法时第i个可选区间所组成的集合；而当算法选择第i个区间时，选的是在可选区间中右端点坐标最小的一个，所以有fi<=gi。证毕。设该算法选出了k个区间，而最优解选出了m个区间。 **命题1.2** 最优解选出的区间数量**m=**该算法选出的区间数量**k**。**** 假设m>k，根据命题1.1，有fk<=gk。由于m>k，必然存在某区间，在gk之后开始，故也在fk之后开始。而该算法一定不会在选了第k个区间后停止，还会选择更多的区间，产生矛盾。所以m<=k,又因为m是最优解选出区间个数，所以m=k。综上所述，算法选出的区间是最优解。 ### 程序实现: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">#include <stdio.h>#include <tchar.h>#include <queue>#include "iostream" using namespace std; const int N = 5;int s[N]={1,2,4,6,8};int t[N]={3,5,7,9,10}; int solve(){pair<int, int> itv[N];for(int i = 0; i < N; i ++) {itv[i].first = s[i];itv[i].second = t[i];}sort(itv, itv + N);int count = 0;int t = 0;for(int i = 0; i < N; i ++) {if(t < itv[i].first) {count ++;t = itv[i].second;}}return count;} int main() {cout << solve() << endl;return 0;}</td></tr></tbody></table> **Java** <table border="1" style="font-family:Simsun; border-collapse:collapse; width:80%; padding:0pt 5.4pt"><tbody><tr><td width="882" valign="top" style="width:661.8pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre code_snippet_id="153733" snippet_file_name="blog_20140112_1_677519" name="code" class="java">package greed; import java.util.Arrays; /** * Created with IntelliJ IDEA. * User: shihuichao * Date: 14-1-14 * Time: 下午10:43 * To change this template use File | Settings | File Templates. */ public class Interval { public static int interval(Work[] works) { Arrays.sort(works); int count = 0; //当前工作的结束时间 int t = 0; for (int i = 0; i < works.length; i++) { if(t < works[i].getStart()) { count ++; t = works[i].getTerminate(); } } return count; } public static void main(String args[]) { Work[] works = { new Work(1, 3), new Work(2, 5), new Work(4, 7), new Work(6, 9), new Work(8, 10) }; int result = interval(works); System.out.println(result); } } class Work implements Comparable { private int start; private int terminate; Work(int start, int terminate) { this.start = start; this.terminate = terminate; } int getStart() { return start; } void setStart(int start) { this.start = start; } int getTerminate() { return terminate; } void setTerminate(int terminate) { this.terminate = terminate; } @Override public int compareTo(Object o) { Work work = (Work) o; if (this.terminate > work.getTerminate()) return 1; else if (this.terminate == work.getTerminate()) return 0; else return -1; } } </pre> </td></tr></tbody></table> **** ### 算法复杂度：时间复杂度 On(nlogn) = 排序O(nlogn) + 扫描O(n)