貪心算法——區間調度問題 · 算法程序設計

貪心算法——區間調度問題 <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)