1210:東東の彼女(二)

2263 ワード

東東にはたくさんの彼女がいることを知っています.彼女たちはみな彼女たちと一緒にいなければならないが、今は東東の彼女たちも毎日授業をしなければならないので、一日中時間があるはずがない.今の問題は、東東の彼女に毎日の暇な時間を与えて、東東が少なくとも何日ですべての彼女と少なくとも1回付き合うことができるかを聞くことです.アルゴリズムを勉強するのに時間がかかりますから.もちろん、東東が彼女と一緒にいる時間帯に別の彼女と一緒にいてはいけない.
最初の数tを入力すると、tグループのテストインスタンスがあり、各グループのテストインスタンスの最初の数n(n<=100)は、東にn人のガールフレンドがいることを示す.次のn行は、各行に2つの数sがあり、eは東の彼女の空き時間の開始時間と終了時間(0出力に必要な最小限の日数で彼女たちと一緒にいます
サンプル入力1 3 1 8 2 3 7
サンプル出力2ソース
2010新生試合
最初は欲張りアルゴリズムを思い浮かべる人が多いかもしれませんが、問題をよく読むと実は少し違います.問題の意味は東東が一日に何人の彼女と付き合うことができるのかではなく、彼が少なくとも何日ですべての彼女と付き合うことができるのかということです.それでは簡単で、直接1つの配列を開いて、時間の重なる部分を累積して、最大で最も少ない時間です.
#include 
#include 
using namespace std;

int main()
{
    int i,mx,t,c[25] = {0},n;
    int a,b;
    scanf("%d",&t);
    while(t--)
    {
        memset(c,0,sizeof(c));

        scanf("%d",&n);

        while(n--)
        {
            scanf("%d %d",&a,&b);
            for(i = a;i <= b;i++)
            {
                c[i]++;

            }
        }

        mx = -1;

        for(i = 0;i <= 24;i++)
            mx = max(c[i],mx);
        printf("%d
"
,mx); } return 0; }