題目的分析被說得有點繞。自己理解是這樣，首先由題目我們知道選擇的區間都是相互不相交的，除這之外，我們的目標是盡量的讓選擇的區間達到最大化。

所以我們可以先對齊排序，因為輸入是隨機的。假設每個區間表示為(x,y)我們可以選擇按照x排序所有區間，也可以選擇按照y來排序所有區間。而不管選擇哪一個來排序，其原理和本質都一樣，都是為了方便操作，將其有序化。

我們這里選擇按照y來排序，排序完后有y1 <= y2 <= y3.......

現在我們討論x1 x2 ....

當x1 > x2時，區間被x2這個區間包含，所以選擇x1這個區間更為劃算。

而當x1 < x2時，當x2 > y1時，區間互不相交，先選x1區間，接著選x2區間

當x1 < x2 && x2 <=y1 時，兩個區間相交，這時，如果選擇了x2區間，就不能選擇x1區間，反之亦然。

但要選擇哪一個呢？我們知道如果不選x2也就是選x1，則我們此時把x1分成兩半部分，一部分在x2內，如果選擇了x2，x2區間不僅包含了x1的，還可能包含x3區間的，因為x2的長度肯定大于或等于x1區間的長度，也就是說從概率上講，選x2肯定不如選x1劃算。

綜上所述：這個問題第一次一定要選擇x1，接著就是把相交部分去掉，循環選不想交的。

#include <stdio.h>typedef struct zone{int x;int y; }zone; zone A[1000]; //快速排序接口 int partition(zone A[],int st,int ed){zone key = A[st];int j = st;for(int i = st + 1; i <= ed; i++){if(A[i].y <= key.y){j++;zone temp = A[i];A[i] = A[j];A[j] = temp;}}zone temp = A[j];A[j] = A[st];A[st] = temp;return j; } void quicksort(zone A[],int st,int ed){if(st < ed){int mid = partition(A,st,ed);quicksort(A,mid + 1,ed);quicksort(A,st,mid - 1);}} //快速排序接口 #define MAXN 1000 int path[MAXN]; int main(){int n;while(scanf("%d",&n) != EOF){for(int i = 0 ; i < n; i++){scanf("%d%d",&A[i].x,&A[i].y);//input (x,y) } quicksort(A,0,n - 1);int len = 0,i = 1;zone key = A[0];path[len++] = 0;while(i < n){if(key.y < A[i].x){//true 則把A[i]拓展進來 path[len++] = i;key = A[i]; } i++;}for(int i = 0; i < len; i++){printf("(%d,%d) ",A[path[i]].x,A[path[i]].y);}}return 0; }

轉載于:https://www.cnblogs.com/sixcoder/archive/2013/04/05/3826017.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的选择不相交区间(贪心算法) By ACReaper的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。