/*

    문제 :

    방문객들을 안내하기 위해 안내원이 투입되어야 한다.

    들어오고 나가는 시각을 정의한 스케쥴이 입력 데이타로 주어질 때,

    최소로 필요한 안내원의 수를 구하여라.

    스케쥴은 안내 시작 시각과 종료 시각 (분 단위라고 가정)으로 주어진다.

    

    풀이 :

    카운터 소트의 본질을 이용.

    동시각에 종료되고 즉시 다른 스케쥴에 투입될 수 있도록, out 을 in 에 우선해

    정렬(카운트)했다. ( out 을 2의 배수로 시각을 만들고, in 은 그보다 1 큰수로 둠 )

    

    시각의 표현 범위(dynamic range) 가 넓으면 카운터 소트가 부적합하다.

    그때는 퀵소트 등으로 구현해주는게 옳다. ( 카운터 소트의 아류인 radix 를 쓸 순 있다 )

*/


#include <iostream>


using namespace std;


typedef struct

{

    size_t in, out; // 방문객이 몇 분에 들어와서 몇 분에 나가는가

}

SCHEDULE;


size_t budget_guides( SCHEDULE* s, const size_t size )

{

    const size_t MAX_TIME   = 60;

    const size_t TABLE_SIZE = ( MAX_TIME + 1 ) * 2;

    int counter_sort_table[TABLE_SIZE] = { 0 };


    for( size_t i = 0; i < size; ++i )

    {

        counter_sort_table[s[i].out * 2    ]++;

        counter_sort_table[s[i].in  * 2 + 1]++;

    }


    size_t guides_max = 0, guides_count = 0;

    for( size_t i = 0; i < TABLE_SIZE; i += 2 )

    {

        guides_count -= counter_sort_table[i    ];

        guides_count += counter_sort_table[i + 1];

        if( guides_max < guides_count ) guides_max = guides_count;

    }

    return guides_max;

}


int main()

{

    SCHEDULE schedules[] =

    {

        { 23, 24 }, { 28, 40 }, { 18, 37 }, { 10, 15 },

        {  3, 23 }, { 25, 31 }, {  1, 17 }, { 21, 29 },

        { 34, 37 }, {  7, 40 },

    };


    cout

        << budget_guides( schedules, sizeof schedules / sizeof *schedules )

        << endl;

    return 0;

}


이거 133t 가 전에 물어서 카페에 올린건데,

똑같은 방법으로 풀 수 있지 않을까?


문제를 다 안읽은건 함정.