Bailian 4100プロセス検出【ソート】

4100:プロセス検出総時間制限:1000 msメモリ制限:65536 kBには、n個のタスクプロセスp 1,p 2,...,pnが記述されており、タスクpiの場合、開始時間はs[i]、終了時間はd[i]である.開始時間と終了時間はいずれも非負の整数であり、100を超えない.実行中のタスクプロセスをテストするモニタTestがあります.Testは毎回テストする時間が短く、無視できます.すなわち、Testが時刻tでテストを行う場合、s[i]<=t<=d[i]を満たすすべてのプロセスpiについて同時にテストが完了する.各プロセスpiは少なくともtestでテストを完了する必要がある.testプログラムのテストの時間を合理的に手配することによって、各プロセスpiが少なくともtestでテストを1回完了する要求を満たすことができ、またtestテストの回数を最小限に抑えることができる.n個のタスクプロセスの開始時間を指定し、testテストの最小回数を与える.第1の動作kが入力され、k組のテスト入力があることを示し、k<100である.各グループの第1の動作nは、n個のプロセス、n<50を表す.次のn行は、各行がスペースで区切られた2つの非負の整数であり、i行目はi番目のプロセスの開始時間s[i]とd[i]、1<=i<=nである.s[i]とd[i]はintタイプで保存できます.出力はテストデータのセットごとに1行出力され、各行の1つの数字はTestプログラムが実行する最小回数である.サンプル入力2 2 1 3 2 4 3 1 3 3 3 4 5サンプル出力1 2
問題リンク:Bailian 4100プロセス検出問題概要:(略)問題分析:簡単なソート処理問題、説明しない.プログラム摘要:(略)参照リンク:(略)題記:(略)
ACのC++言語プログラムは以下の通りである.

/* Bailian4100   */

#include 

using namespace std;

const int N = 50;
struct Process {
     
    int start, end;
} p[N];

bool cmp(Process a, Process b)
{
     
    return a.end < b.end;
}

int main()
{
     
    int k, n;
    scanf("%d", &k);
    while(k--) {
     
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            scanf("%d%d", &p[i].start, &p[i].end);

        sort(p, p + n, cmp);

        int cnt = 0;
        for(int i = 0, j; i < n; ) {
     
            for(j = i; p[j].start <= p[i].end && j < n; j++);
            i = j;
            cnt++;
        }

        printf("%d
", cnt);
    }

    return 0;
}