題目簡述：

有n個(gè)區(qū)間，輸入每個(gè)區(qū)間的開頭和結(jié)尾，求出最多且沒有重疊的區(qū)間數(shù)

知識(shí)點(diǎn)考察：

貪心算法

思路：

不重復(fù)區(qū)間這種題型要先按照每個(gè)區(qū)間的結(jié)尾從小到大排序

這樣的排序有兩種情況出現(xiàn):

1. 第一個(gè)區(qū)間的頭小于第二個(gè)區(qū)間的頭

2. 第一個(gè)區(qū)間的頭大于第二個(gè)區(qū)間的頭

這個(gè)兩種情況中的任意一種都是要選擇第一個(gè)區(qū)間的，接下來就考慮要不要選擇下面的區(qū)間的問題：如果第一個(gè)區(qū)間的尾大于第二個(gè)區(qū)間的頭那么第二個(gè)區(qū)間就不選，用第一個(gè)區(qū)間的尾循環(huán)跟全部區(qū)間的頭對比一次，將頭比第一個(gè)區(qū)間尾大的區(qū)間全都篩除，然后再用第二個(gè)沒有被篩掉的區(qū)間跟剩下的區(qū)間去比較。。。

中間用計(jì)數(shù)變量記住可以選上的區(qū)間的數(shù)量，最后輸出

易錯(cuò)點(diǎn)：

第一次嘗試時(shí)我是把區(qū)間頭尾差從小到大排序，并且用數(shù)組模擬區(qū)間來記錄是否重復(fù)，如果數(shù)組的計(jì)數(shù)>1就讓ans++,這個(gè)經(jīng)過多次判斷之后就會(huì)出錯(cuò)，而且用了冒泡排序（采購趕緊去學(xué)排序?。。?/p>

代碼：

#include <iostream>

#include <algorithm>/*sort排序*/

using namespace std;

const long long MAX=10000000;

struct information{

? ? long long a,b;

}zu[MAX];

int vis[MAX],ans;

bool com(information q,information p)/*sort排序的函數(shù)，用來排序區(qū)間的尾部*/

{

? ? return q.b<p.b;

}

int main()

{

? ? int n;

? ? cin>>n;

? ? for(int i=0;i<n;i++)cin>>zu[i].a>>zu[i].b;/*輸入*/

? ? sort(zu,zu+n,com);/*排序*/

? ? for(int i=0;i<n;i++){

? ? ? ? if(!vis[i]){//判斷是不是已經(jīng)被篩除或者已經(jīng)被選中

? ? ? ? ? ? ans++;

? ? ? ? ? ? vis[i]=1;//被選中標(biāo)記為1

? ? ? ? ? ? for(int j=i+1;j<n;j++){

? ? ? ? ? ? ? ? if(zu[i].b>zu[j].a){//如果前一個(gè)的尾大于后面的頭就篩除

? ? ? ? ? ? ? ? ? ? vis[j]=1;//篩除標(biāo)記為1

? ? ? ? ? ? ? ? }

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? cout<<ans;

}