區間完全覆蓋問題
例題1
描述：給定一個長度為m的區間，再給出n條線段的起點和終點（注意這裡是閉區間），求最少使用多少條線段可以將整個區間完全覆蓋
樣例：
區間長度8，可選的覆蓋線段[2,6],[1,4],[3,6],[3,7],[6,8],[2,4],[3,5]
解題過程:
1將每一個區間按照左端點遞增順序排列，拍完序後為[1,4]，[2,4]，[2,6]，[3,5]，[3,6]，[3,7]，[6,8]
2設置一個變量表示已經覆蓋到的區域。再剩下的線段中找出所有左端點小於等於當前已經覆蓋到的區域的右端點的線段中，右端點最大的線段在加入，直到已經覆蓋全部的區域
3過程:
假設第一步加入[1,4]，那麼下一步能夠選擇的有[2,6]，[3,5]，[3,6]，[3,7]，由於7最大，所以下一步選擇[3,7]，最後一步只能選擇[6,8]，這個時候剛好達到了8退出，所選區間為3
4貪心證明:
需要最少的線段進行覆蓋，那麼選取的線段必然要盡量長，而已經覆蓋到的區域之前的地方已經無所謂了，（可以理解成所有的可以覆蓋的左端點都是已經覆蓋到的地方），那麼真正能夠使得線段更成的是右端點，左端點沒有太大的意義，所以選擇右端點來覆蓋
例題2
有n個閉區間[ai,bi]，其中i=1，2，……，n。這些區間代表一系列沒有交點的閉區間。任務是去尋找這些區間的代表，力求僅需最少的區間數覆蓋整個區間。這些區間代表應該以上升的順序寫在輸出文件。我們說區間[a，b]和[c，d]是上升的順序是指當且僅當a≤b≤c≤d。
輸入：
第一行有一個整數n，3≤n≤50000，這是區間數目。在第i+1行，1≤i≤n，有一個區間[ai,bi]的描述，描述的形式是以兩個由空格分隔開的ai,bi表示，ai，bi分別表示區間的開始和結束，1≤ai≤bi≤1000000。
輸出：
所有計算出的沒有交點的區間。在第一行都有一個區間的描述。它包含2個整數，整數間由空格分開，區的開始與結束都是獨立的。這些區間應該以上升的順序輸出。
三． 啟發與總結：
將無序的區間轉化成有序的區間使本題的關鍵。將沒有條理（無序）的已知條件轉化為有條理（有序）的已知條件是一種重要思想，在拿到一道無從下手的題目時這樣做往往能起到很好的作用。
排序雖然在近幾年不是競賽中的熱點問題，但它也經常在各種考試中出現，在許多問題中都要用到排序，所以一定要熟練掌握各種排序算法。
區間均取最少2個點的問題：
給定一個大區間[a,b]，再給出幾個小區間 ，找出滿足下述條件的所含元素個數最少的集合的個數，該集合滿足
——對於給定的每一個區間，都至少有兩個不同的整數屬於該集合。
本題數據規模較大，用搜索做會超時，而動態規劃無從下手。考慮貪心算法。題目意思是要找一個集合，該集合中的數的個數既要少又要和所給定的所有區間都有2個點的交集。（每個區間至少有兩個該集合中的數）。我們可以從所給的區間中選數，為了選盡量少的數，應該使所選的數和更多的區間有交集這就是貪心的標准。一開始將所有區間按照右端點從小到大排序。從第一個區間開始逐個向後檢查，看所選出的數與所查看的區間有無交集，有兩個則跳過，只有一個數相交，就從當前區間中選出最大的一個數（即右端點），若無交集，則從當前區間選出兩個數，就（右端點，右端點-1），直至最後一個區間。
[cpp]
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct prince
{
int left,right;//區間左右端點
}a[10000];
int n;
int result;//存放結果中的數
int cmp(const void *a,const void *b)
{
return (*(prince *)a).right-(*(prince *)b).right;
}
int work()
{
qsort(a+1,n,sizeof(a[0]),cmp);//按區間右端點由小到大排序
int i;
int a1,a2;
a1=a[1].right-1;a2=a[1].right;result=2;
for(i=2;i<=n;i++)
{
if(a[i].left<=a1&& a[i].right>=a2)continue;//完全包含的情況下 其區間的2點就是上次的2點 直接跳過
if (a[i].left>a2 )//完全不包含 則要添加進去2點
{
a1=a[i].right-1;a2=a[i].right;result=result+2;
}
if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2)
{
a1=a2;a2=a[i].right;result++;}//只包含一個
}
return result;
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++)
scanf("%d %d",&a[i].left,&a[i].right);
printf("%d\n",work());
return 0;
}
