wikioi-天梯-普及一等-貪心-1214：線段覆寫

題目描述 Description

    給定x軸上的N（0<N<100）條線段，每個線段由它的二個端點a_I和b_I确定，I=1,2,……N.這些坐标都是區間（－999，999）的整數。有些線段之間會互相交疊或覆寫。請你編寫一個程式，從給出的線段中去掉盡量少的線段，使得剩下的線段兩兩之間沒有内部公共點。所謂的内部公共點是指一個點同時屬于兩條線段且至少在其中一條線段的内部（即除去端點的部分）。

輸入描述 Input Description

    輸入第一行是一個整數N。接下來有N行，每行有二個空格隔開的整數，表示一條線段的二個端點的坐标。

輸出描述 Output Description

    輸出第一行是一個整數表示最多剩下的線段數。

樣例輸入 Sample Input

3

6  3

1  3

2  5

樣例輸出 Sample Output

2

資料範圍及提示 Data Size & Hint

0<N<100

類型：貪心  難度：1.5

題意：見上述

分析：又考慮多了的一道題。。

先将線段排序，先按線段起點排序，若起點相同按終點排序，都是由小到大，依次周遊線段判斷是否保留。

設目前線段為[ai,bi]，之前保留的線段的最右邊的點為now，考慮以下情況：

1、ai>=now，即目前線段和之前保留的線段不重疊，那麼直接保留目前線段（ans++），更新now=bi

2、ai<now，目前線段和之前保留的線段有重疊，再分情況考慮：

（1）若bi<=now，證明目前線段完全被之前保留線段的區域包含（因為已經排序，是以目前線段的起點一定大于等于之前的線段，bi<now證明終點小于等于之前線段，是以被包含），那麼證明目前線段更優（一條線段被另一條完全包含，顯然取短的線段更優，即貪心），更新now=bi，但是結果計數（ans）不變

（2）若bi>now，證明目前線段一部分和之前重疊，一部分不重疊，那麼為了對後續線段影響最小，即now盡量小，用貪心法則，目前線段被舍棄，結果計數（ans）不變

ps：開始用sort排序，發現sort無法直接對二維數組排序，是以用qsort排序了

代碼：

#include<iostream>
#include<algorithm>
using namespace std;

int cmp(const void *x,const void *y)
{
    int *a = (int*)x,*b = (int*)y;
    if(a[0]==b[0]) return a[1]-b[1];
    return a[0]-b[0];
}

int main()
{
    int n,ave=0,a[110][2];
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int l,r;
        cin>>l>>r;
        if(l<r) 
        {
            a[i][0] = l;
            a[i][1] = r;
        }
        else
        {
            a[i][0] = r;
            a[i][1] = l;
        }
    }
    qsort(a,n,sizeof(int)*2,cmp);
    /*
    for(int i=0; i<n; i++)
    {
        cout<<a[i][0]<<" "<<a[i][1]<<endl;
    }*/
    int ans = 1,now = a[0][1];
    for(int i=1; i<n; i++)
    {
        if(a[i][0]>=now)
        {
            ans++;
            now = a[i][1];
        }
        else
        {
            if(a[i][1]<now) now = a[i][1];
        }
    }
    
    cout<<ans<<endl;
}