(C++) 백준 9576 책 나눠주기

https://www.acmicpc.net/problem/9576

그리디하게 접근해야 한다. 갖고싶은 책의 범위가 1. 작은 수부터 2. 짧은 순으로 정렬하고 정렬 된 앞에서부터 한권씩 준다.

위의 조건에 맞게 정렬하면 다음처럼 정렬되고, 정렬된 수의 앞에서부터 비어있는 순으로 책을 배분하면 최대로 만족하는 수를 구할 수 있다.

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

bool book[1001];

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.second != b.second) return a.second < b.second;
    return a.first<b.first;
}

int main(){
    int T; cin>>T;

    while(T--){
        int N,M;
        memset(book, false, sizeof(book));


        cin>>N>>M;
        vector<pair<int, int>> v(M);

        for(int i=0; i<M; i++) {
            int a,b;
            cin>>a>>b;
            v[i]= {a,b};
        }
        sort(v.begin(), v.end(), cmp);

        
        int ans=0;
        for(auto & i : v){
            int x = i.first;
            int y = i.second;
            for(int j=x; j<=y; j++){
                if(!book[j]) {
                    book[j]=true;
                    ans++;
                    break;
                }
            }
        }
        cout<<ans<<'\n';
    }
}