[백준]: 1931번: 회의실 배정 / 탐욕적 기법(Greedy Algorithm)

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

처음 이 문제를 접근할 때, 문제를 제대로 읽지않아 3번의 "틀렸습니다." 보게 되었다.

- 시간에 따라서 배열에 visit하고 visit되었다면 cnt를 증가시키지않는다. 시간은 2^31-1보다 작은 자연수이기 떄문에 int형으로 담기에는 한계가 있다. => 접근부터가 잘못되었음.

간단하게 생각하면 끝나는 시간이 빠른 순서대로 수행하면 된다.

=> deque<pair>에 (끝나는 시간, 시작시간) 순으로 입력받는다. -> 이후, 정렬을 수행한다.(끝나는 시간이 빠른 기준으로 정렬) ->

 시작하는 시간 <=끝나는 시간 (카운터 증가,) -> 반복

#include<iostream>

using namespace std;

#include<algorithm>

#include<deque>

#include<utility>

int n;

deque <pair<int, int>> v;

int cnt;

int main()

{

cin >> n;

int a, b;

for (int i = 1; i <= n; i++)

{

cin >> a >> b;

v.push_back(pair<int, int>(b, a));

}

sort(v.begin(), v.end());

int earily = 0;

while (!v.empty())

{

int start = v.front().second;

int end = v.front().first;

if (earily <= start)

{

earily = end;

cnt++;

}

v.pop_front();

}

cout << cnt << endl;

return 0;

}