백준 11000 강의실 배정

강의실 배정 문제다. 그리디를 통해 구현해내면 되는데, 방법은 금방 떠올릴 수 있는데 priority queue 를 사용하는 구현에 있어서 애를 좀 먹었다.

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

 

이렇게 적는게 priority queue 를 작은 순으로 만드는 방법이다.

 

  pq.push(arr[0].second);
  for (int i = 1; i < n; i++)
  {
    pq.push(arr[i].second);
    if (pq.top() <= arr[i].first)
      pq.pop();
  }

정렬한 순으로 끝나는 시간을 pq에 차례로 넣어줄 것인데, 만약 pq 에서 가장 top 의 값 (가장 먼저 끝나는 수업) 보다 현재 넣고자 하는 강의가 시작하는 시간이 더 크거나 같다면, pq 의 top 을 없애주고 새로운 강의를 집어 넣어주는 방식으로 구현할 수 있었다.