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

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

해당문제를 해결하기위해 초기에 이중포문을 사용하여 

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

{

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

{

if (room[i] <= v[j].first)

{

room[i] = v[j].second;

if (cnt < i)

cnt = i;

break;

}

}

}

printf("%d\n", cnt);

비교를 하려고 하였으나, n의범위가 200000*200000번의 반복문수행이 발생하기에 시간초과가 발생하였다.

따라서 이 문제를 해결하기 위해서 O(nlogn)시간의 수행하도록 설정하여야 했다.

해결방법

1. pair로 first,second // 시작시간, 끝나는 시간 을 입력받는다.

2. 시작시간을 기준으로 정렬한다.

3. 맨처음에 있는 끝나는 시간(가장빨리시작하는)을 넣는다.

4. for을 수행( //수업중인 강의실의 끝나는 시간 > 다음 수업 시작시간 => 강의실 추가(우선순위 큐 push), 아니라면 pop)

#include<cstdio>

#include<algorithm>

#include<queue>

#include<functional>

using namespace std;

typedef pair <int, int> intpair;

// 시작, 끝시간 입력 -> sort(시작시간 오름차순)

// 같은 시간일떄 끝나는 시간 오름차순 정렬

int main()

{

int cnt=0, n;

scanf("%d", &n);

intpair *v = new intpair[n+1];

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

{

scanf("%d %d", &v[i].first, &v[i].second);

}

sort(v, v + n + 1);

priority_queue<int, vector<int>, greater<int>>pq;

pq.push(v[0].second); //정렬을 했으니까, 맨 처음끝나는 시간을 넣는다.

int start, end;

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

{

start = v[i].first;

end = v[i].second;

if (pq.top() > start)

{

pq.push(end);

} //수업중인 강의실의 끝나는 시간 > 다음 수업 시작시간 => 강의실 추가

else

{

pq.pop(); // 아니면 나가고 다음꺼 수행

pq.push(end);

}

}

printf("%d\n", pq.size());

return 0;

}