백준 : 1931*

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

1931번: 회의실배정

#include<iostream>
#include<algorithm>
using namespace std;
int N;
pair<int,int> p[100001];

bool compare(pair<int,int> &p1,pair<int,int> &p2){
    if(p1.second == p2.second) return p1.first < p2.first;
    else return p1.second<p2.second;

}


int main(void){
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>p[i].first>>p[i].second;
    }

    sort(p,p+N,compare);
    
    int cnt=0;
    int locate=0;

    for(int i=0;i<N;i++){
        if(locate <= p[i].first){
            ++cnt;
            locate = p[i].second;
        }
    }

    cout<<cnt;
}

 

문제유형 : 그리디

시간의 최대값이 2^31이므로 dp로 접근할수 없다.

따라서 그리디로 접근한다.

 

1. 회의시간 시작시간이 짧은 순으로 정렬후 처리

- 반례 : 제일빨리시작하는 경우가 가장 늦게 끝날 경우

 

2. 회의시간이 짧은 경우

- 반례 : 가장 회의시간이 짧은 회의가 그다음 순번에 있는 회의 사이에 있어서 두회의를 못하게 하는 경우

 

3. 회의 끝나는 시간이 짧은 순으로 정렬후 처리

- 반례: 없음

- 회의시간이 빨리 끝나는 순으로 먼저처리한다면 앞으로 사용 할 시간이 많게 되니 자연적으로 회의 시간이 빨리 끝나는 경우로 처리하는 경우가 가장 많은 회의를 할수 있는 경우가 된다.