2016 SDAUレッスン1_1004

1.タイトル番号1004
2.単純な問題Input入力データは複数のテストインスタンスを含み、各テストインスタンスの最初の行は1つの整数n(n<=100)しかなく、あなたが好きな番組の総数を表し、次いでn行のデータであり、各行は2つのデータTi_を含むs,Ti_e(1<=i<=n)は、i番目の番組の開始時間と終了時間をそれぞれ表し、問題を簡略化するために、各時間を正の整数で表す.n=0は入力終了を示し、処理を行わない.Outputは、各テストインスタンスについて、完全に見えるテレビ番組の個数を出力し、各テストインスタンスの出力が1行を占める.
3.問題を解く構想形成過程の授業で貪欲アルゴリズムに関する最初の例題は、原題を少し変更した.構想形成過程でなければ欲張りアルゴリズムの解題パターンである.1)タイトルは欲張りアルゴリズム2)でソートするのに適している.終了時間順に3)を選択します.終了時間が最も早い番組を1つ目とし,2つ目の番組開始時間が1つ目の番組終了時間よりも大きく,条件を満たす番組を選択された番組とすることで,4)結果を推す.旧問題論題,問題は手配可能な番組の個数を出力するだけで,(3)ステップでカウントできる.最終出力結果
4.感想は原題どおりにして、別に何の感じもしないで、復習しましょう
5.コード

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

struct TV
{

    int Ti_start;
    int Ti_end;
    bool b;     
};

bool cmp(const TV &a,const TV &b)
{
    return a.Ti_end<=b.Ti_end;
}

int main()
{   
// ifstream cin("nrj.txt");
    int n;

    while(cin>>n)
    {
        if(n==0)    break;
        vector<TV> tv(n);
        vector<TV>::iterator it1,it2;

        for(int i=0;i<n;i++)
        {
            cin>>tv[i].Ti_start;
            cin>>tv[i].Ti_end;
            tv[i].b=0;
        }

        sort(tv.begin(),tv.end(),cmp);

        it2=tv.begin();
        (*it2).b=1;

        int p=1;
        for(it1=tv.begin()+1;it1!=tv.end();it1++)       
        {
            if((*it2).b=1&&(*it1).Ti_start>=(*it2).Ti_end)
            {
                (*it1).b=1;
                it2=it1;
                p++;            
            }   
        }
        cout<<p<<endl;
    }
}