[[problem:NERD2]]
문제를 풀다가 코드를 책에 나온 것과 거의 동일하게 했는데
시간 초과가 나더라고요.
차이점이 있다면 책에는 map< int, int > coord를 전역변수로 설정했었고, 저는 메인 함수 안에다 선언하고 함수를 호출할 때마다 인자로 넘겨줬습니다.
그래서 책에 나온 방식대로 하니 되더라고요.

왜 이렇게 차이가 나는 건가요?
map< int, int > coord를 인자로 넘겨주는게 시간이 그렇게 오래 걸리나요?

코드는 아래와 같습니다.

#include <cstdio>
#include <map>

#pragma warning(disable:4996)

using namespace std;

bool IsDominated(map<int, int> coords, int a, int b){
    map<int, int>::iterator cit = coords.upper_bound(a);

    if (cit == coords.end())
        return false;
    return b < cit->second;
}

void RemoveDominated(map<int, int> &coords, int a, int b){
    map<int, int>::iterator cit = coords.lower_bound(a);

    if (cit == coords.begin()) return;
    cit--;
    while (true){
        if (cit->second > b) break;
        if (cit == coords.begin()){
            coords.erase(cit);
            break;
        }
        else{
            map<int, int>::iterator cit2 = cit;
            cit2--;
            coords.erase(cit);
            cit = cit2;
        }
    }
    return;
}

int CountPpl(map<int, int> &coords, int a, int b){

    // 지배당하면 필요없다
    if (!IsDominated(coords, a, b)){
        // 지배하는 것들 지우기
        RemoveDominated(coords, a, b);
        //coords.insert(coords.end(), make_pair(a, b));
        coords[a] = b;
    }       
    return coords.size();
}

int main(void){
    //freopen("input.txt", "r", stdin);
    int tc, ppl;
    map<int, int> coords;
    scanf("%d", &tc);

    for (int i = 0; i < tc; i++){
        scanf("%d", &ppl);
        int a, b, count = 0;
        coords.clear();
        for (int j = 0; j < ppl; j++){
            scanf("%d %d", &a, &b);
            if (j == 0){
                coords[a] = b;
                count += 1;
                continue;
            }
            count += CountPpl(coords, a, b);
        }
        printf("%d\n", count);
    }

    return 0;
}